On graphic degree sequences and matching numbers

Tamás Róbert Mezei, Shubha R. Kharel, Péter L. Erdős, Zoltán Toroczkai

Published 2022-04-15Version 1

In this paper we study the relationship between the degree sequence of a graph and its matching number. First, we prove that whether a degree sequence can be extended with a new degree $\delta$ is equivalent to the existence of a realization of the original degree sequence with a matching of size $\delta/2$ that covers the largest $\delta$ degrees. Second, we estimate the minimum size of both the maximal and the maximum matching, as determined by the degree sequence, for any realization. Furthermore, we also estimate the maximum value of the matching number over all possible realizations for the degree sequence. Along this line we answer a question raised by Biedl, Demaine et al. (DOI:10.1016/j.disc.2004.05.003). These results are all closely connected to the recently introduced family of Degree Preserving Growth graph-dynamics (DOI:10.1038/s41567-021-01417-7).