TY - GEN
A1 - Petrosyan Petros
PB - Elsevier
N2 - In 2010, Mkrtchyan, Petrosyan, and Vardanyan proved that every graph G with 2≤δ(G)≤Δ(G)≤3 contains a maximum matching M such that no two vertices uncovered by M share a neighbor, where Δ(G) and δ(G) denote the maximum and minimum degrees of vertices in G, respectively. In the same paper they suggested the following conjecture: every graph G with Δ(G)−δ(G)≤1 contains a maximum matching M such that no two vertices uncovered by M share a neighbor. Recently, Picouleau disproved this conjecture by constructing a bipartite counterexample G with Δ(G)=5 and δ(G)=4. In this note, we show that the conjecture is false for graphs G with Δ(G)−δ(G)=1 and Δ(G)≥4, and for r-regular graphs when r≥7.
L1 - http://noad.sci.am/Content/136139/44.pdf
L2 - http://noad.sci.am/Content/136139
T1 - On maximum matchings in almost regular graphs
UR - http://noad.sci.am/dlibra/docmetadata?id=136139
ER -