Cyclic Hamiltonian cycle systems for the complete multipartite graph
Francesca Merola
Roma Tre University, Italy
Anita Pasotti
Universit\`a degli Studi di Brescia, Italy
Marco A. Pellegrini
Universit\`a Cattolica del Sacro Cuore, Italy
Michael W. Schroeder
Marshall University, USA
PDF
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.