\(C_{p}\)-decompositions of some regular graphs (Q2368932): Difference between revisions

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