Partition of a complete directed graph into hamiltonian cycles

Question

I would like to take the $n\left(n - 1\right)$ edges of a complete directed graph on n vertices and partition them into $n - 1$ disjoint hamiltonian cycles.

For example, on $n = 5$, this can be done with the sets $$ \begin{array}{c} \{(1,2), (2,3), (3,4), (4,5), (5,1)\}, \\[1mm] \{(1,3), (3,5), (5,2), (2,4), (4,1)\}, \\[1mm] \{(1,4), (4,2), (2,5), (5,3), (3,1)\}, \\[1mm] \{(1,5), (5,4), (4,3), (3,2), (2,1)\}. \end{array} $$

Most immediately, I want such a solution for N=6. I suspect no such solution exists. In that case, I would like to know for which N this is and is not possible.

One can trivially construct such solutions for prime N by doing the following: Arrange the vertices in a circle. WLOG label them in ascending order clockwise as 1, 2, ... p-1, p. For the 1st set, start with vertex 1, go one position clockwise to 2, and so add edge (1,2). then from 2 go one position clockwise to 3 and so add edge (2,3), etc until (p-1, p), (p, 1). For the 2nd set, go 2 positions clockwise to generate each edge. 2 is coprime with p so you will hit every vertex before coming back to 1. For the 3rd set, go 3 positions clockwise each time. For the kth set, go k positions clockwise each time. Since p is prime, it is coprime with every k<p, so each of the p-1 sets will cycle through all of the vertices.

This procedure doesn't work for composite N e.g 6, because you go (1,3) (3,5) (5,1) and you're back to 1 without hitting 2, 4, 6.

If you use undirected hamiltonian cycles, it is possible to find 5 such that they represent each edge twice like so. However, in the case of this solution and every other one I've found, when you direct the edges, you must either repeat an edge direction, or have the graphs not be cyclic.

I could brute-force the solution for 6, but I am hoping there is some elegant construction or proof of impossibility that generalizes to larger N.

Answer 1

For odd $n$, we always get a decomposition of the edges of $K_n$ into disjoint Hamilton cycles. This has a very nice "visual" proof: simply "rotate" the cycle drawn below around the vertex in the middle.

The image is taken from the paper [A08] where this and several related constructions are discussed. Clearly this gives a decomposition of the complete directed graph (by taking both orientations of each of the Hamilton cycles).

If $n$ is even, and $n \geq 8$ there is also a Hamilton decomposition of the complete directed graph, see [T80].

So $n=4$ and $n=6$ are the only missing cases, and they are indeed the only instances where no Hamilton decomposition exists (as you note, this can be verified e.g. by brute force case distinction).

[A08] Alspach, Brian, The wonderful Walecki construction, Bull. Inst. Comb. Appl. 52, 7-20 (2008). ZBL1157.05035.

[T80] Tillson, Timothy W., A Hamiltonian decomposition of (K^*_{2m},2m\geq 8), J. Comb. Theory, Ser. B 29, 68-74 (1980). ZBL0439.05025.