Maximum matchings in regular graphs

DOI10.1016/J.DISC.2018.01.016MaRDI QIDQ1709508zbMATH OpenOpenAlexFDO

Authors Peng Zhang

Publication date 5 April 2018

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

regular graphsmaximum matching

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: It was conjectured by Mkrtchyan, Petrosyan, and Vardanyan that every graph $G$ with $Delta(G)-delta(G)le1$ has a maximum matching $M$ such that any two $M$-unsaturated vertices do not share a neighbor. In this note, we confirm the conjecture for all $k$-regular simple graphs and also $k$-regular multigraphs with $kle4$.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 3220175 (Why is no real title available?)
• A note on a conjecture on maximum matching in almost regular graphs
• Corrigendum to: ``On disjoint matchings in cubic graphs
• Matching theory
• On disjoint matchings in cubic graphs
• On maximum matchings in almost regular graphs
• Paths, Trees, and Flowers

Cited in

(11)

• 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
• Second kind maximum matching graph
• scientific article; zbMATH DE number 7339006 (Why is no real title available?)
• Finding a maximum matching in a permutation graph
• scientific article; zbMATH DE number 4114698 (Why is no real title available?)
• Maximum matchings in geometric intersection graphs
• On maximum matchings in König-Egerváry graphs
• On maximal matchings of connected graphs
• On maximum matchings in almost regular graphs

This page was built for publication: Maximum matchings in regular graphs

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