On maximum matchings in almost regular graphs

Details On maximum matchings in almost regular graphs On maximum matchings in almost regular graphs

2012-02-03

arxiv.org/abs/1202.0681v1

Mathematics

Combinatorics

3 pages

Scientific paper

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 disprove this conjecture in a general form.

Affiliated with

Also associated with

No associations

Rating

On maximum matchings in almost regular graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On maximum matchings in almost regular graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On maximum matchings in almost regular graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-4603