Path and cycle decompositions of complete equipartite graphs: 3 and 5 parts

Abstract: In 1998 Cavenagh [N.J. Cavenagh, Decompositions of complete tripartite graphs into -cycles, Australas. J. Combin. 18 (1998) 193–200] gave necessary and sufficient conditions for the existence of an edge-disjoint decomposition of a complete equipartite graph with three parts, into cycles of some fixed length . Here we extend this to paths, and show that such a complete equipartite graph with three partite sets of size , has an edge-disjoint decomposition into paths of length if and only if divides and . Further, extending to five partite sets, we show that a complete equipartite graph with five partite sets of size has an edge-disjoint decomposition into cycles (and also into paths) of length with if and only if divides and for cycles (or for paths). [Copyright &y& Elsevier]