The Hamilton-Waterloo Problem with even cycle lengths

Abstract

The Hamilton-Waterloo Problem HWP$(v;m,n;\alpha ,\beta )$ asks for a 2-factorization of the complete graph $K_v$ or $K_v-I$, the complete graph with the edges of a 1-factor removed, into $\alpha$ $C_m$-factors and $\beta$ $C_n$-factors, where $3\le m<n$. In the case that $m$ and $n$ are both even, the problem has been solved except possibly when $1\in \{\alpha ,\beta \}$ or when $\alpha$ and $\beta$ are both odd, in which case necessarily $v\equiv 2(\mathrm{mod}4)$. In this paper, we develop a new construction that creates factorizations with larger cycles from existing factorizations under certain conditions. This construction enables us to show that there is a solution to HWP$(v;2m,2n;\alpha ,\beta )$ for odd $\alpha$ and $\beta$ whenever the obvious necessary conditions hold, except possibly if $\beta =1$; $\beta =3$ and $\gcd (m,n)=1$; $\alpha =1$; or $v=2mn/\gcd (m,n)$. This result almost completely settles the existence problem for even cycles, other than the possible exceptions noted above.