
06250575
j
06250575
Petrosyan, Petros A.
On maximum matchings in almost regular graphs.
Discrete Math. 318, 5861 (2014).
2014
Elsevier Science B.V. (NorthHolland), Amsterdam
EN
bipartite graph
regular graph
maximum matching
Zbl 1200.05178
Zbl 1200.05181
doi:10.1016/j.disc.2013.11.019
Summary: In [ibid. 310, No. 1011, 15881613 (2010; Zbl 1200.05178); corrigendum ibid. 313, No. 21, 2381 (2013)], {\it V. V. Mkrtchyan} et al. proved that every graph $G$ with $2\leq\delta (G)\leq\varDelta (G)\leq 3$ contains a maximum matching $M$ such that no two vertices uncovered by $M$ share a neighbor, where $\varDelta (G)$ and $\delta (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 $\varDelta (G)\delta (G)\leq 1$ contains a maximum matching $M$ such that no two vertices uncovered by $M$ share a neighbor. Recently, {\it C. Picouleau} [ibid. 310, No. 24, 36463647 (2010; Zbl 1200.05181)] disproved this conjecture by constructing a bipartite counterexample $G$ with $\varDelta (G)=5$ and $\delta (G)=4$. In this note, we show that the conjecture is false for graphs $G$ with $\varDelta (G)\delta (G)=1$ and $\varDelta (G)\geq 4$, and for $r$regular graphs when $r\geq 7$.