×

Complete equipartite \(3p\)-cycle systems. (English) Zbl 1207.05108

Summary: Necessary conditions for decomposing a complete equipartite graph \(K_n*\overline K_m\) (having \(n\) parts of size \(m\)) into cycles of a fixed length \(k\) are that \(nm\geq k\), the degree of all its vertices are even and its total number of edges is a multiple of \(k\). Determining whether these necessary conditions are sufficient for general cycle length \(k\) is an open problem. Recent results by R. S. Manikandan and P. Paulraja [Discrete Math. 306, No. 4, 429–451 (2006; Zbl 1087.05048)] and B. R. Smith [J. Comb. Des. 16, No. 3, 244–252 (2008; Zbl 1149.05026)] proved the sufficiency of these conditions in cases where the cycle length is respectively an odd prime or twice an odd prime. Here we further extend these results by showing the sufficiency of these conditions for decomposing complete equipartite graphs into cycles of length \(3p\) (where \(p\) is an odd prime), thus providing the first general family of results for non-prime, odd length cycle decompositions of this type.

MSC:

05C38 Paths and cycles