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

In this paper we show that the complete equipartite graph with nn parts, each of size 2k2k, decomposes into cycles of length λ2λ2 for any even n≥4n≥4, any integer k≥3k≥3 and any odd λλ such that 3≤λ<2nk and λλ divides kk. 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 p2p2, where pp is prime. In proving our main result, we have also shown the following. Let λ≥3λ≥3 and n≥4n≥4 be odd and even integers, respectively. Then there exists a decomposition of the λλ-fold complete equipartite graph with nn parts, each of size 2k2k, into cycles of length λλ if and only if λ<2knλ<2kn. In particular, if we take the complete graph on 2n2n vertices, remove a 11-factor, then increase the multiplicity of each edge to λλ, the resultant graph decomposes into cycles of length λλ if and only if λ<2nλ<2n.