Published April 8, 2022
| Version v1
Journal article
Factorially Many Maximum Matchings Close to the Erdős-Gallai Bound
Contributors
Others:
- Algorithmes, Graphes et Combinatoire (ALGCO) ; Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM) ; Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)
- Universität Ulm - Ulm University [Ulm, Allemagne]
- Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
- ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)
Description
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)$.
Abstract
International audienceAdditional details
Identifiers
- URL
- https://hal.inria.fr/hal-03701284
- URN
- urn:oai:HAL:hal-03701284v1