On the Hamilton-Waterloo problem: the case of two cycles sizes of different parity

Abstract

The Hamilton-Waterloo problem asks for a decomposition of the complete graph into $r$ copies of a 2-factor $F_1$ and $s$ copies of a 2-factor $F_2$ such that $r+s=\lfloor \frac{v-1}{2}\rfloor$. If $F_1$ consists of $m$-cycles and $F_2$ consists of $n$ cycles, then we call such a decomposition a $(m,n)-$HWP$(v;r,s)$. The goal is to find a decomposition for every possible pair $(r,s)$. In this paper, we show that for odd $x$ and $y$, there is a $(2^{k}x,y)-$HWP$(vm;r,s)$ if $\gcd (x,y)\ge 3$, $m\ge 3$, and both $x$ and $y$ divide $v$, except possibly when $1\in \{r,s\}$.

12 Pages