\(C_{p}\)-decompositions of some regular graphs. (English) Zbl 1087.05048

Let \(C_n\) denote the cycle of length \(n\). A \(C_n\)-decomposition of a graph \(X\) is a partition of its edge set so that each part is isomorphic to \(C_n\). A \(C_n\)-factorization of a graph \(X\) is a partition of its edge set into 2-factors \(F_1,F_2,\dots,F_d\) such that each \(F_i\) is a vertex-disjoint union of cycles \(C_n\). Let \(K_{m(n)}\) denote the complete multipartite graph with \(m\) parts each having cardinality \(n\). A long-standing conjecture is that the obvious arithmetical conditions for \(K_{m(n)}\) to admit a \(C_t\)-decomposition are, in fact, sufficient. This paper essentially adresses the conjecture and establishes several nice results. The most striking result is that \(K_{m(n)}\) admits a \(C_p\)-decomposition, where \(p\) is a prime bigger than 10, if and only if \(n(m-1)\) is even and \(p\) divides \(m(m-1)n^2\).


05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI


[1] Alspach, B.; Gavlas, H., Cycle decompositions of \(K_n\) and \(K_n - I\), J. combin. theory ser. B, 81, 77-99, (2001) · Zbl 1023.05112
[2] Alspach, B.; Schellenberg, P.J.; Stinson, D.R.; Wagner, D., The oberwolfach problem and factors of uniform odd length cycles, J. combin. theory ser. A, 52, 20-43, (1989) · Zbl 0684.05035
[3] Billington, E.J., Decomposing complete tripartite graphs into cycles of length 3 and 4, Discrete math., 197/198, 123-135, (1999) · Zbl 0930.05072
[4] Billington, E.J.; Hoffman, D.G.; Maenhaut, B.M., Group divisible pentagon systems, Utilitas math., 55, 211-219, (1999) · Zbl 0938.05020
[5] Cavenagh, N.J., Decompositions of complete tripartite graphs into \(k\)-cycles, Austral. J. combin., 18, 193-200, (1998) · Zbl 0924.05051
[6] Cavenagh, N.J.; Billington, E.J., Decompositions of complete multipartite graphs into cycles of even length, Graphs combin., 16, 49-65, (2000) · Zbl 0944.05083
[7] Cavenagh, N.J.; Billington, E.J., On decomposing complete tripartite graphs into 5-cycles, Austral. J. combin., 22, 41-62, (2000) · Zbl 0965.05078
[8] Lindner, C.C.; Rodger, C.A., Decomposition into cycles II: cycle systems, (), 325-369 · Zbl 0774.05078
[9] Lindner, C.C.; Rodger, C.A., Design theory, (1997), CRC Press New York · Zbl 0926.68090
[10] Liu, J., The equipartite oberwolfach problem with uniform tables, J. combin. theory ser. A, 101, 20-34, (2003) · Zbl 1015.05074
[11] E.S. Mahmoodian, M. Mirzakhani, Decomposition of complete tripartite graphs into 5-cycles, in: C.J. Colbourn, E.S. Mahmoodian (Eds.), Combinatorics and Advances, 1995. · Zbl 0837.05088
[12] R.S. Manikandan, P. Paulraja, \(C_5\)-decompositions of some regular graphs, submitted for publication. · Zbl 1120.05071
[13] R.S. Manikandan, P. Paulraja, \(C_7\)-decompositions of some regular graphs, submitted for publication. · Zbl 1366.05081
[14] Muthusamy, A.; Paulraja, P., Factorizations of product graphs into cycles of uniform length, Graphs combin., 11, 69-90, (1995) · Zbl 0822.05054
[15] Piotrowski, W.L., The solution of the bipartite analogue of the oberwolfach problem, Discrete math., 97, 339-356, (1991) · Zbl 0765.05080
[16] Šajna, M., Cycle decompositions III: complete graphs and fixed length cycles, J. combin. designs, 10, 27-78, (2002) · Zbl 1033.05078
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.