Cyclic Hamiltonian cycle systems for the complete multipartite graph

Minisymposium: GENERAL SESSION TALKS

Content: A Hamiltonian cycle system (HCS) for a graph or multigraph $\Gamma$ is a set $\cal B$ of Hamiltonian cycles of $\Gamma$ whose edges partition the edge set of $\Gamma$. A cycle system is {\em regular} if there is an automorphism group $G$ of the graph $\Gamma$ acting sharply transitively on the vertices of $\Gamma$ and permuting the cycles of ${\cal B}$, and it is called {\em cyclic} if $G$ is the cyclic group. The existence problem for cyclic HCS for the complete graph $K_n$, $n$ odd, and for the graph $K_{2n}-I$, $I$ a 1-factor, (the so-called {\em cocktail party graph}), has been solved by Buratti and Del Fra (2004), and Jordon and Morris (2008) respectively. In the talk I will consider existence results for cyclic Hamiltonian cycle systems for $K_{m\times n}$, the complete multipartite graph with $m$ parts, each of size $n$. I will present necessary and sufficient conditions for the existence of a cyclic HCS for the graph $K_{m\times n}$ when the number of parts $m$ is even, and more generally for $mn$ even, and discuss some work in progress for the case in which both $m$ and $n$ are odd. I will also touch on the symmetric HCS introduced by Brualdi and Schroeder in 2011 for the cocktail party graph, and recently generalized by Schroeder to complete multipartite graphs; indeed we may note that cyclic cycle systems often turn out to possess this additional symmetry requirement, so that it makes sense to discuss these results in this context.

Back to all abstracts