Path factorizations of complete multipartite graphs Original Research Article

It is shown that the necessary conditions mn ≡ 0 (mod k) and (m − 1)nk ≡ 0 (mod 2(k − 1)) for Km ∗ Kn, the wreath product of Km and Kn, to have a Pk-factorization are sufficient when k = p + 1, p a prime. This answers a problem of Yu on Pk-factorizations of complete multipartite graphs, when k = prime + 1.