Cyclic hamiltonian cycle systems of the complete multipartite graph: even number of parts

Abstract

A hamiltonian cycle system (HCS, for short) of a graph $\Gamma$ is a partition of the edges of $\Gamma$ into hamiltonian cycles. A HCS is cyclic when it is invariant under a cyclic permutation of all the vertices of $\Gamma$; the existence problem for a cyclic HCS has been completely solved by Buratti and Del Fra in 2004 when $\Gamma$ is the complete graph $K_v$, $v$ odd, and by Jordon and Morris in 2008 when $\Gamma$ is the complete graph minus a $1$-factor $K_v-I$, $v$ even. In this work we present a complete solution to the existence problem of a cyclic HCS for $\Gamma =K_{m\times n}$, the complete multipartite graph, when the number of parts $m$ is even. We also give necessary and sufficient conditions for the existence of a cyclic and symmetric HCS of $\Gamma$; the notion of a symmetric HCS of a graph $\Gamma$ has been introduced in 2004 by Akiyama, Kobayashi, and Nakamura for $\Gamma =K_v$, $v$ odd, in 2011 by Brualdi and Schroeder when $\Gamma =K_v-I$, $v$ even, and, very recently, by Schroeder when $\Gamma$ is the complete multipartite graph.

14 pages