A characterization of graphs with given maximum degree and smallest possible matching number

DOI10.1016/j.disc.2021.112426zbMath1466.05036OpenAlexW3152564265MaRDI QIDQ2032746

Zekhaya B. Shozi, Michael A. Henning

Publication date: 14 June 2021

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

Full work available at URL: https://doi.org/10.1016/j.disc.2021.112426

zbMATH Keywords

matching numbermaximum degreefactor-critical graph

Mathematics Subject Classification ID

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

Related Items (2)

A characterization of graphs with given maximum degree and smallest possible matching number. II ⋮ A generalization of Petersen's matching theorem

Cites Work

• Induced matchings in subcubic graphs without short cycles
• Independent sets and matchings in subcubic graphs
• Matching and edge-connectivity in regular graphs
• A short proof of the Berge-Tutte formula and the Gallai-Edmonds structure theorem
• Matching theory
• Tight bounds on maximal and maximum matchings
• Uniquely restricted matchings in subcubic graphs
• Tight lower bounds on the size of a maximum matching in a regular graph
• Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree
• Tight lower bounds on the matching number in a graph with given maximum degree
• Total Domination in Graphs
• On Lower Bounds for the Matching Number of Subcubic Graphs
• A characterization of the subcubic graphs achieving equality in the Haxell‐Scott lower bound for the matching number
• Unnamed Item
• Unnamed Item

This page was built for publication: A characterization of graphs with given maximum degree and smallest possible matching number