Article ID Journal Published Year Pages File Type
8902979 Discrete Mathematics 2018 4 Pages PDF
Abstract
It was conjectured by Mkrtchyan, Petrosyan and Vardanyan that every graph G with Δ(G)−δ(G)≤1 has a maximum matching M such that any two M-unsaturated vertices do not share a neighbor. The results obtained in Mkrtchyan et al. (2010), Petrosyan (2014) and Picouleau (2010) leave the conjecture unknown only for k-regular graphs with 4≤k≤6. All counterexamples for k-regular graphs (k≥7) given in Petrosyan (2014) have multiple edges. In this paper, we confirm the conjecture for all k-regular simple graphs and also k-regular multigraphs with k≤4.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,