Matching and edge-connectivity in graphs with given maximum degree

DOI10.1016/J.DISC.2021.112438MaRDI QIDQ2032857zbMATH OpenOpenAlexFDO

Authors Michael A. Henning, A. Yeo

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

zbMATH Keywords

edge-connectivitymatching numbermaximum degree

Mathematics Subject Classification ID

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

Recommendations

• Tight lower bounds on the matching number in a graph with given maximum degree
• Matching and edge-connectivity in regular graphs
• Tight bound for matching
• Tight lower bounds on the size of a maximum matching in a regular graph
• A characterization of graphs with given maximum degree and smallest possible matching number. II

Cites work

• A characterization of the subcubic graphs achieving equality in the Haxell‐Scott lower bound for the matching number
• A complete description of convex sets associated with matchings and edge‐connectivity in graphs
• 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
• Edge-connectivity, eigenvalues, and matchings in regular graphs
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 863471 (Why is no real title available?)
• Independent sets and matchings in subcubic graphs
• Matching and edge-connectivity in regular graphs
• Matching theory
• Matchings in regular graphs from eigenvalues
• Maximum matchings in a regular graph of specified connectivity and bounded order
• New lower bounds for matching numbers of general and bipartite graphs
• 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

Cited in

(16)

• A characterization of graphs with given maximum degree and smallest possible matching number. II
• A generalization of Petersen's matching theorem
• Reducing the maximum degree of a graph: comparisons of bounds
• Matching for Graphs of Bounded Degree
• Generalization of Erdős-Gallai edge bound
• Maximal matchings in graphs with large neighborhoods of independent vertices
• scientific article; zbMATH DE number 4114698 (Why is no real title available?)
• Maximum number of edges in claw-free graphs whose maximum degree and matching number are bounded
• The lower bound on the number of maximum matchings of a graph
• New lower bounds for matching numbers of general and bipartite graphs
• Minimum number of vertices of graphs without perfect matching, with given edge connectivity and minimum and maximum degrees
• scientific article; zbMATH DE number 2226732 (Why is no real title available?)
• On the maximum number of edges in chordal graphs of bounded degree and matching number
• A complete description of convex sets associated with matchings and edge‐connectivity in graphs
• Matching and edge-connectivity in regular graphs
• On maximal matchings of connected graphs

This page was built for publication: Matching and edge-connectivity in graphs with given maximum degree

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