Some gregarious cycle decompositions of complete equipartite graphs
The electronic journal of combinatorics, Tome 16 (2009) no. 1
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.
DOI :
10.37236/224
Classification :
05C38, 05C51
Mots-clés : \(k\)-cycle decomposition of a multipartite graph, gregarious cycles of prime length
Mots-clés : \(k\)-cycle decomposition of a multipartite graph, gregarious cycles of prime length
@article{10_37236_224,
author = {Benjamin R. Smith},
title = {Some gregarious cycle decompositions of complete equipartite graphs},
journal = {The electronic journal of combinatorics},
year = {2009},
volume = {16},
number = {1},
doi = {10.37236/224},
zbl = {1230.05182},
url = {http://geodesic.mathdoc.fr/articles/10.37236/224/}
}
Benjamin R. Smith. Some gregarious cycle decompositions of complete equipartite graphs. The electronic journal of combinatorics, Tome 16 (2009) no. 1. doi: 10.37236/224
Cité par Sources :