On the Hamilton-Waterloo problem with odd cycle lengths

Andrea Burgess
University of New Brunswick

Peter Danziger
Ryerson University

Tommaso Traetta
Ryerson University



Content: The Hamilton-Waterloo problem $\mathrm{HWP}(K_v;m,n;\alpha,\beta)$ asks whether there exists a decomposition of $K_v$ into $\alpha$ $m$-cycle factors and $\beta$ $n$-cycle factors, where $3 \leq m \leq n$. Necessarily, if such a decomposition exists, then $m$, $n$ and $v$ are all odd, $m$ and $n$ are divisors of $v$, and $\alpha+\beta=(v-1)/2$. We show that these necessary conditions are sufficient whenever $m \geq 5$, $v$ is a multiple of $mn$ and $v>mn$, except possibly if $\beta \in \{1,3\}$. For $m \geq 5$ and $v=mn$, we solve the problem whenever $\beta > (n+5)/2$, except possibly if $(v,m,n,\alpha,\beta)=(35,5,7,9,8)$. Similar results are obtained when $m=3$, with only a few extra possible exceptions in this case. Our results rely on the existence of factorizations of $C_m[n]$ (the lexicographic product of an $m$-cycle with the complement of $K_n$), which will be further discussed in Tommaso Traetta's talk.

Back to all abstracts