The Hamilton-Waterloo Problem with 4-Cycles and a Single Factor of n-Cycles

Abstract

A 2-factor in a graph G is a 2-regular spanning subgraph of G, and a 2-factorization of G is a decomposition of all the edges of G into edge-disjoint 2-factors. A -factorization of K (upsilon) asks for a 2-factorization of K (upsilon) , where r of the 2-factors consists of m-cycles, and s of the 2-factors consists of n-cycles. This is a case of the Hamilton-Waterloo problem with uniform cycle sizes m and n. If upsilon is even, then it is a decomposition of K (upsilon) - F where a 1-factor F is removed from K (upsilon) . We present necessary and sufficient conditions for the existence of a -factorization of K (upsilon) - F.