Nomadic decompositions of bidirected complete graphs (Q932653)

A nomadic Hamiltonian decomposition of a bidirected complete graph on n vertices is a Hamiltonian decomposition with the nomads walk along the Hamiltonian cycles without colliding. Similarly, a nomadic near-Hamiltonian decomposition is the one in which the cycles in the decomposition have length \(n-1\). Let \(n\) be prime. A bidirected complete graph can be decomposed into \(n-1\) directed cycles such that all of the edges within each cycle have the same length. For this decomposition, it is shown that any two nomads will collide regardless of their initial positions. The author shows that a bidirected complete graph of \(n\) vertices has a nomadic near-Hamiltonian decomposition for every \(n\) not equal to \(2 \mod 4\).