pith. sign in

arxiv: 1202.0681 · v2 · pith:6N3MXUXSnew · submitted 2012-02-03 · 🧮 math.CO · cs.DM

On maximum matchings in almost regular graphs

classification 🧮 math.CO cs.DM
keywords deltamaximumconjecturegraphsverticescommoncontainsevery
0
0 comments X
read the original abstract

In 2010, Mkrtchyan, Petrosyan and Vardanyan proved that every graph $G$ with $2\leq \delta(G)\leq \Delta(G)\leq 3$ contains a maximum matching whose unsaturated vertices do not have a common neighbor, where $\Delta(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 $\Delta(G)-\delta(G)\leq 1$ contains a maximum matching whose unsaturated vertices do not have a common neighbor. Recently, Picouleau disproved this conjecture by constructing a bipartite counterexample $G$ with $\Delta(G)=5$ and $\delta(G)=4$. In this note we show that the conjecture is false for graphs $G$ with $\Delta(G)-\delta(G)=1$ and $\Delta(G)\geq 4$, and for $r$-regular graphs when $r\geq 7$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.