The Hamilton-Waterloo Problem with Triangle-factors and Hamilton Cycles: The case \(n \equiv 3 \pmod{6}\)

Alan C.H.Ling1, J.H. Dinitz2
1Dept. of Computer Science University of Vermont Burlington, Vermont
2Dept. of Mathematics and Statistics University of Vermont Burlington, Vermont

Abstract

The Hamilton-Waterloo problem in the case of triangle-factors and Hamilton cycles asks for a \(2\)-factorization of \( K_n \), in which each \(2\)-factor is either a Hamilton cycle or a triangle-factor. Necessarily \( n \equiv 3 \pmod{6} \). The case of \( n \equiv 9 \pmod{18} \) was completely solved in 2004 by Horak, Nedela, and Rosa. In this note, we solve the problem when \( n \equiv 3 \pmod{18} \) and there are at least two Hamilton cycles. A companion paper treats the case when there is exactly one Hamilton cycle and \( n \equiv 3 \pmod{6} \).