The Disjoint $1$-Factors of $(d,d+1)$-Graphs

Abstract

A graph $G$ is called $(d,d+1)$-graph if the degree of every vertex of $G$ is either $d$ or $d+1$. In this paper, the following results are proved:
A $(d,d+1)$-graph $G$ of order $2n$ with no $1$-factor and no odd component, satisfies $|V(G)|\ge 3d+4$;A $(d,d+1)$-graph $G$ of order $2n$ with $d(G)\ge n$, contains at least $[(n+2)/3]+(d-n)$ edge disjoint $1$-factors.These results generalize the theorems due to W. D. Wallis, A. I. W. Hilton and C. Q. Zhang.