Decomposing complete equipartite graphs into odd square-length cycles: Number of parts even

In this paper we show that the complete equipartite graph with n parts, each of size 2k, decomposes into cycles of length lambda(2) for any even n >= 4, any integer k >= 3 and any odd lambda such that 3 <= lambda < root 2nk and lambda divides k. As a corollary, we obtain necessary and sufficient conditions for the decomposition of any complete equipartite graph with an even number of parts into cycles of length p(2), where p is prime. In proving our main result, we have also shown the following. Let lambda >= 3 and n >= 4 be odd and even integers, respectively. Then there exists a decomposition of the lambda-fold complete equipartite graph with n parts, each of size 2k, into cycles of length A if and only if lambda < 2kn. In particular, if we take the complete graph on 2n vertices, remove a 1-factor, then increase the multiplicity of each edge to lambda. the resultant graph decomposes into cycles of length lambda if and only if lambda < 2n. (C) 2012 Elsevier B.V. All rights reserved.