Nomadic Decompositions of Bidirected Complete Graphs

Abstract

We use $K_n^{\ast }$ to denote the bidirected complete graph on $n$ vertices. A nomadic Hamiltonian decomposition of $K_n^{\ast }$ is a Hamiltonian decomposition, with the additional property that ``nomads'' walk along the Hamiltonian cycles (moving one vertex per time step) without colliding. A nomadic near-Hamiltonian decomposition is defined similarly, except that the cycles in the decomposition have length $n-1$, rather than length $n$. J.A. Bondy asked whether these decompositions of $K_n^{\ast }$ exist for all $n$. We show that $K_n^{\ast }$ admits a nomadic near-Hamiltonian decomposition when $n\not\equiv 2\mathrm{mod}4$.