Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8902979 | Discrete Mathematics | 2018 | 4 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Dong Ye,