Maximum matchings in regular graphs

DOI10.1016/J.DISC.2018.01.016zbMATH Open1383.05265arXiv1308.2269OpenAlexW2963405002MaRDI QIDQ1709508FDOQ1709508

Authors: Peng Zhang 

Publication date: 5 April 2018

Published in: Discrete Mathematics (Search for Journal in Brave)

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$.

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

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

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)

Cites Work

• Matching theory
• Paths, Trees, and Flowers
• Title not available (Why is that?)
• Corrigendum to: ``On disjoint matchings in cubic graphs
• On maximum matchings in almost regular graphs
• A note on a conjecture on maximum matching in almost regular graphs
• On disjoint matchings in cubic graphs

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
• Title not available (Why is that?)
• Finding a maximum matching in a permutation graph
• Title not available (Why is that?)
• 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)