×

Some gregarious cycle decompositions of complete equipartite graphs. (English) Zbl 1230.05182

Summary: A \(k\)-cycle decomposition of a multipartite graph \(G\) is said to be gregarious if each \(k\)-cycle in the decomposition intersects \(k\) distinct partite sets of \(G\). In this paper we prove necessary and sufficient conditions for the existence of such a decomposition in the case where \(G\) is the complete equipartite graph, having \(n\) parts of size \(m\), and either \(n \equiv 0, 1 \pmod k\), or \(k\) is odd and \(m \equiv 0 \pmod k\). As a consequence, we prove necessary and sufficient conditions for decomposing complete equipartite graphs into gregarious cycles of prime length.

MSC:

05C38 Paths and cycles
05C51 Graph designs and isomorphic decomposition
PDFBibTeX XMLCite
Full Text: EuDML EMIS