Journal of the
Korean Mathematical Society JKMS

The complete multipartite graph $K_{n(2t)}$ having $n$ partite sets of size $2t$, with $n\geq6$ and $t\geq 1$, is shown to have a decomposition into $gregarious$ $6$-cycles, that is, the cycles which have at most one vertex from any particular partite set. Complete sets of differences of numbers in $\mathbb Z_n$ are used to produce starter cycles and obtain other cycles by rotating the cycles around the $n$-gon of the partite sets.

Keywords: multipartite graph, graph decomposition, gregarious cycle, difference set

MSC numbers: 05B10, 05C38, 05C70