A generalization of Petersen's matching theorem

DOI10.1016/J.DISC.2022.113263MaRDI QIDQ2111920zbMATH OpenOpenAlexWikidataFDO

Authors Michael A. Henning, Zekhaya B. Shozi

Publication date 17 January 2023

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

matching numbermaximum degree2-connected graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Recommendations

• A characterization of graphs with given maximum degree and smallest possible matching number
• On maximum matchings in cubic graphs with a bounded number of bridge-covering paths
• Independent sets and matchings in subcubic graphs
• Minimum maximal matchings in cubic graphs
• A characterization of graphs with given maximum degree and smallest possible matching number. II
• Matching and edge-connectivity in regular graphs
• Tight lower bounds on the size of a maximum matching in a regular graph
• Perfect matchings and \(K_{1,p}\)-restricted graphs
• Maximum matchings in a regular graph of specified connectivity and bounded order
• Perfect matchings in graphs with prescribed local restrictions

Cites work

• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• A characterization of graphs with given maximum degree and smallest possible matching number
• A characterization of graphs with given maximum degree and smallest possible matching number. II
• A characterization of the subcubic graphs achieving equality in the Haxell‐Scott lower bound for the matching number
• A short proof of the Berge-Tutte formula and the Gallai-Edmonds structure theorem
• Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree
• Congruent Graphs and the Connectivity of Graphs
• Edge-connectivity, eigenvalues, and matchings in regular graphs
• Independent sets and matchings in subcubic graphs
• Induced matchings in subcubic graphs without short cycles
• Matching and edge-connectivity in graphs with given maximum degree
• Matching and edge-connectivity in regular graphs
• Matching theory
• On Lower Bounds for the Matching Number of Subcubic Graphs
• Tight bounds on maximal and maximum matchings
• Tight lower bounds on the matching number in a graph with given maximum degree
• Tight lower bounds on the size of a maximum matching in a regular graph
• Total domination in graphs
• Uniquely restricted matchings in subcubic graphs

Cited in

(9)

• The Monochromatic Circumference of 2‐Edge‐Colored Graphs
• The Petersen matroid
• A generalization of Petersen's theorem
• A proof of Petersen's theorem
• Perfect matchings in graphs with prescribed local restrictions
• Perfect matchings and \(K_{1,p}\)-restricted graphs
• Variations on a theorem of Petersen
• On maximum matchings in cubic graphs with a bounded number of bridge-covering paths
• Efficient algorithms for Petersen's matching theorem

This page was built for publication: A generalization of Petersen's matching theorem

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