Hamilton decompositions of complete multipartite graphs with any 2‐factor leave

For m  ≥ 1 and p  ≥ 2, given a set of integers s 1 ,…, s q with $s_j \geq p+1$ for $1 \leq j \leq q$ and ${\sum _{j\,=\,1}^q} s_j = mp$ , necessary and sufficient conditions are found for the existence of a hamilton decomposition of the complete p ‐partite graph $K_{m,\ldots,m} - E(U)$ , where U is a 2‐factor of $K_{m,\ldots,m}$ consisting of q cycles, the j th cycle having length s j . This result is then used to completely solve the problem when p  = 3, removing the condition that $s_j\ge p+1$ . © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 208–214, 2003