The maximum number of perfect matchings of semi-regular graphs

Abstract

Let $n\ge 34$ be an even integer, and $D_n=2\lceil n/4\rceil -1$. In this paper, we prove that every $\{D_n,D_n+1\}$-graph of order $n$ contains $\lceil n/4\rceil$ disjoint perfect matchings. This result is sharp in the sense that (i) there exists a $\{D_n,D_n+1\}$-graph containing exactly $\lceil n/4\rceil$ disjoint perfect matchings, and that (ii) there exists a $\{D_n-1,D_n\}$-graph without perfect matchings for each $n$. As a consequence, for any integer $D\ge D_n$, every $\{D,D+1\}$-graph of order $n$ contains $\lceil (D+1)/2\rceil$ disjoint perfect matchings. This extends Csaba et~al.'s breathe-taking result that every $D$-regular graph of sufficiently large order is $1$-factorizable, generalizes Zhang and Zhu's result that every $D_n$-regular graph of order $n$ contains $\lceil n/4\rceil$ disjoint perfect matchings, and improves Hou's result that for all $k\ge n/2$, every $\{k,k+1\}$-graph of order $n$ contains $(\lfloor n/3\rfloor +1+k-n/2)$ disjoint perfect matchings.

arXiv comment30 pages, 9 figures