On maximum matchings in almost regular graphs

DOI10.1016/J.DISC.2013.11.019MaRDI QIDQ394310zbMATH OpenOpenAlexFDO

Authors P. A. Petrosyan

Publication date 27 January 2014

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.0681

zbMATH Keywords

bipartite graphmaximum matchingregular graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: In 2010, Mkrtchyan, Petrosyan and Vardanyan proved that every graph $G$ with $2leqdelta(G)leqDelta(G)leq3$ 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)leq1$ 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)geq4$, and for $r$-regular graphs when $rgeq7$.

Recommendations

• Maximum matchings in regular graphs
• A note on a conjecture on maximum matching in almost regular graphs
• On maximum matchings in 5-regular and 6-regular multigraphs
• Maximum matchings in regular graphs of high girth
• Maximum matchings in a regular graph of specified connectivity and bounded order

Cites work

• A note on a conjecture on maximum matching in almost regular graphs
• Matching theory
• On disjoint matchings in cubic graphs
• The Factorization of Linear Graphs

Cited in

(15)

• Maximum matchings in regular graphs
• Characterizations of maximum matching graphs of certain types
• On maximum matchings in 5-regular and 6-regular multigraphs
• On maximum matchings in König-Egerváry graphs
• Tight lower bounds on the size of a maximum matching in a regular graph
• Results and open problems in matchings in regular graphs
• Corrigendum to: ``On disjoint matchings in cubic graphs
• Maximal matchings in graphs with large neighborhoods of independent vertices
• On extension of regular graphs
• scientific article; zbMATH DE number 279491 (Why is no real title available?)
• scientific article; zbMATH DE number 5053297 (Why is no real title available?)
• Maximum matchings in geometric intersection graphs
• A note on a conjecture on maximum matching in almost regular graphs
• On maximal matchings of connected graphs
• Maximum matchings in regular graphs of high girth

This page was built for publication: On maximum matchings in almost regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q394310)