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

It is proved that a complete tripartite graph with all partite sets of size \(m\) has an edge-disjoint decomposition into paths of length \(k\) if and only if \(k\) divides \(3m^2\) and \(k<3m\). This extends a previous result on decomposition into cycles of lengths \(k\) by \textit{N. J. Cavenagh} [``Decompositions of complete tripartite graphs into \(k\)-cycles'', Australas. J. Comb. 18, 193--200 (1998; Zbl 0924.05051)]. It is also proved that a complete multipartite graph with five partite sets of size \(m\) has an edge-disjoint decomposition into paths (and also cycles) of length \(k\) with \(k\geq 3\) if and only if \(k\) divides \(10m^2\) and \(k<5m\) (or \(k\leq 5m\) for cycles).