pith. sign in

arxiv: 1810.02009 · v3 · pith:K33KNQUNnew · submitted 2018-10-04 · 🧮 math.CO

The Hamilton-Waterloo Problem with even cycle lengths

classification 🧮 math.CO
keywords betaalphaproblemevencasecompleteconditionsconstruction
0
0 comments X
read the original 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 \leq 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 \pmod{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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.