Graphs with restricted valency and matching number

DOI10.1016/J.DISC.2008.10.007MaRDI QIDQ1043593zbMATH OpenOpenAlexFDO

Authors Niranjan Balachandran, Niraj Khare

Publication date 9 December 2009

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

factor-critical graphGallai's lemmasunflower

Mathematics Subject Classification ID

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

Abstract: Consider the family of all finite graphs with maximum degree $Delta(G)<d$ and matching number $u(G)<m$. In this paper we give a new proof to obtain the exact upper bound for the number of edges in such graphs and also characterize all the cases when the maximal graph is unique. We also provide a new proof of Gallai's lemma concerning factor critical graphs.

Recommendations

• Graphs with given valences
• scientific article; zbMATH DE number 2151975
• Graphs with the fewest matchings
• Graphs in which some and every maximum matching is uniquely restricted
• Matching preclusion number of graphs
• On the number of matchings in regular graphs
• Counting matchings in graphs
• On matchings in graphs
• scientific article; zbMATH DE number 695765
• Number of induced matchings of graphs

Cites work

• Degrees and matchings
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• scientific article; zbMATH DE number 970806 (Why is no real title available?)
• Intersection Theorems for Systems of Sets
• Intersection theorems for systems of sets
• Matching theory

Cited in

(21)

• The size of 3-uniform hypergraphs with given matching number and codegree
• Graphs whose edge set can be partitioned into maximum matchings
• Graphs with given valences
• Maximum size of a graph with given fractional matching number
• The Turán number for the edge blow-up of trees
• Extremal graphs for edge blow-up of graphs
• On the size of 3-uniform linear hypergraphs
• Graph classes and Ramsey numbers
• Generalization of Erdős-Gallai edge bound
• Maximum number of edges in claw-free graphs whose maximum degree and matching number are bounded
• On the maximum number of edges in chordal graphs of bounded degree and matching number
• On the maximum number of edges in chordal graphs of bounded degree and matching number
• On the maximum number of edges in planar graphs of bounded degree and matching number
• Strong chromatic index and Hadwiger number
• Turán graphs with bounded matching number
• On generalized Turán numbers of intersecting cliques
• Maximum size of connected graphs with bounded maximum degree and matching number
• Constructing extremal triangle-free graphs using integer programming
• Extremal problems for a matching and any other graph
• Anti-Ramsey number of the star and matching family
• Restricted matching in graphs of small genus

This page was built for publication: Graphs with restricted valency and matching number

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