The maximum number of perfect matchings of semi-regular graphs

preprint2015arXivOpen access

Abstract

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

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.