On the Hamilton-Waterloo Problem with odd orders

Abstract

Given non-negative integers $v,m,n,\alpha ,\beta$, the Hamilton-Waterloo problem asks for a factorization of the complete graph $K_v$ into $\alpha$ $C_m$-factors and $\beta$ $C_n$-factors. Clearly, $v$ odd, $n,m\ge 3$, $m\mid v$, $n\mid v$ and $\alpha +\beta =(v-1)/2$ are necessary conditions. To date results have only been found for specific values of $m$ and $n$. In this paper we show that for any $m$ and $n$ the necessary conditions are sufficient when $v$ is a multiple of $mn$ and $v>mn$, except possibly when $\beta =1$ or 3, with five additional possible exceptions in $(m,n,\beta )$. For the case where $v=mn$ we show sufficiency when $\beta >(n+5)/2$ except possibly when $(m,\alpha )=(3,2)$, $(3,4)$, with seven further possible exceptions in $(m,n,\alpha ,\beta )$. We also show that when $n\ge m\ge 3$ are odd integers, the lexicographic product of $C_m$ with the empty graph of order $n$ has a factorization into $\alpha$ $C_m$-factors and $\beta$ $C_n$-factors for every $0\le \alpha \le n$, $\beta =n-\alpha$, except possibly when $\alpha =2,4$, $\beta =1,3$, with three additional possible exceptions in $(m,n,\alpha )$.

39 pages

References in corpus (1)

• On the Hamilton-Waterloo Problem with triangle factors and $C_{3x}$-factors

Cited by in corpus (2)

• The Hamilton-Waterloo Problem for $C_3$-factors and $C_n$-factors
• Infinitely many cyclic solutions to the Hamilton-Waterloo problem with odd length cycles