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

Autor:	Stéphane Bessy, Johannes Pardey, Lucas Picasarri-Arrieta, Dieter Rautenbach
Rok vydání:	2022
Předmět:	Computational Theory and Mathematics Applied Mathematics Discrete Mathematics and Combinatorics Geometry and Topology Theoretical Computer Science
Zdroj:	The Electronic Journal of Combinatorics. 29
ISSN:	1077-8926
DOI:	10.37236/10610
Popis:	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)$.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::1aae74881a8d05338d08655e40f7220d https://doi.org/10.37236/10610 Zobrazit plný text záznamu