Decomposition of complete multipartite graphs into disjoint unions of cycles

Abstract

Let G be a 2-regular graph of odd order n and let v be a positive integer. It is of interest to know when there exists a G-decomposition of Kv. If v ≡ 1 or n (mod 2n), then v satis es the necessary conditions for the existence of a Gdecomposition of Kv. If G contains exactly one odd cycle, it is known that there exists a G-decomposition of Kv for all v ≡ 1 (mod 2n). In this dissertation, we focus on G-decompositions of complete multipartite graphs. For positive integers r and s, let Kr×s denote the complete multipartite graph with r parts of order s each. We use a novel extension of the Bose construction for Steiner triple systems to show that there exists a G-decomposition of K(2k+1)×n for every positive integer k and a G-decomposition of Kk′×2n for every integer k′ ≥ 3. Furthermore, if G has only two components, we nd G-decompositions of Kv for all v ≡ n (mod 2n) unless G = C4 ∪ C5 and v = 9. Additionally, if G consists of three odd cycles, we nd G-decompositions of K(2k+1)×n for every positive integer k, of Kk′×2n for every integer k′ ≥ 3, and of Kv for all v ≡ 1 (mod 2n), except v = 4n + 1.