The Hamilton-Waterloo problem with cycle sizes of different parity

ADRIÁN PASTINE; MELISSA KERANEN

Conferencia; Graphs, groups, and more: celebrating Brian Alspach?s 80th and Dragan Maru?ič?s 65th birthdays; 2018

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=\left\lfloor\frac{v-1}{2}\right\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)$. This problem has been studied in great depth in the cases when $m$ and $n$ have the same parity, but there are few general results for the case of different parity.In this work, we use rings of polynomials of the form $\mathbb{Z}_{2^{n}}[x]/\left\langle x^2+x+1\right\rangle$ to show that for odd $x$ and $y$, there is a $(2^kx,y)-$HWP$(vm;r,s)$ if $\gcd(x,y)\geq 3$, $m\geq 3$, and both $x$ and $y$ divide $v$, except possibly when $1\in\{r,s\}$.