On maximum matchings in 5-regular and 6-regular multigraphs

In 2010, Mkrtchyan, Petrosyan and Vardanyan made the conjecture that every graph G with Δ(G)−δ(G)≤1 has a maximum matching M such that no two vertices uncovered by M share a neighbor. The results obtained by Mkrtchyan et al. (2010) [4], Picouleau (2010) [6], Petrosyan (2014) [5] and Ye (2018) [8] le...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2023-02, Vol.346 (2), p.113243, Article 113243
Main Author: Abrahamyan, Sevak
Format: Article
Language:English
Subjects:
Bipartite graph
Maximum matching
Regular multigraph
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In 2010, Mkrtchyan, Petrosyan and Vardanyan made the conjecture that every graph G with Δ(G)−δ(G)≤1 has a maximum matching M such that no two vertices uncovered by M share a neighbor. The results obtained by Mkrtchyan et al. (2010) [4], Picouleau (2010) [6], Petrosyan (2014) [5] and Ye (2018) [8] leave the conjecture unknown only for 5-regular and 6-regular multigraphs. In this paper, we confirm the conjecture for these two cases.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2022.113243