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

  • Stéphane Bessy
  • Johannes Pardey
  • Lucas Picasarri-Arrieta
  • Dieter Rautenbach

Abstract

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)$.

Published
2022-06-17
Article Number
P2.52