Factorially many maximum matchings close to the Erdős-Gallai bound

2021/07/31 by Stéphane Bessy, Bessy, Stéphane, Johannes Pardey +5
Computer Science · Economics, Econometrics and Finance · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Game Theory and Voting Systems #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2108.00134

openalex publication_date 2021/07/31 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28

Abstract

A classical result of Erdős and Gallai determines the maximum size m(n,ν) of a graph G of order n and matching number νn. We show that G has factorially many maximum matchings provided that its size is sufficiently close to m(n,ν).

Related

• Two lower bounds for maximum matching
• Enumeration of maximum matchings of graphs
• Structure of the largest subgraphs of G_n,p with a given matching number
• The average size of maximal matchings in graphs
• Generalizations of the Erdős Matching Conjecture for the t-Matching Number