Logo image
Se connecter
Factorially Many Maximum Matchings Close to the Erdős-Gallai Bound
Article de revue   Open Access

Factorially Many Maximum Matchings Close to the Erdős-Gallai Bound

Stéphane Bessy, Johannes Pardey, Lucas Picasarri-Arrieta et Dieter Rautenbach
The Electronic Journal of Combinatorics, Vol.29(2)
08/04/2022

Résumé

A classical result of Erdős and Gallai 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)$.

Fichiers et liens (2)

url
Find in HALAfficher
url
https://doi.org/10.37236/10610Afficher
Published (Version of record) Ouvrir

Indicateurs

1 Consultations de la notice

Détails

Logo image