Factorially many maximum matchings close to the Erdős-Gallai bound (Q2152791)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Factorially many maximum matchings close to the Erdős-Gallai bound |
scientific article |
Statements
Factorially many maximum matchings close to the Erdős-Gallai bound (English)
0 references
11 July 2022
0 references
Summary: A classical result of \textit{P. Erdős} and \textit{T. Gallai} [Acta Math. Acad. Sci. Hung. 10, 337--356 (1959; Zbl 0090.39401)] determines the maximum size \(m(n,\nu)\) of a graph \(G\) of order \(n\) and matching number \(\nu n\). We show that \(G\) has factorially many maximum matchings provided that its size is sufficiently close to \(m(n,\nu)\).
0 references
matching number
0 references
maximum matchings
0 references
0 references