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

Manikandan, R. S.; Paulraja, P.

Discrete Math. 306, No. 4, 429-451 (2006).

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\).

Reviewer: Brian Alspach (Regina)

MSC:

05C70

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

cycle decomposition; factorization; tensor product; complete multipartite graph

References:

[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