Decompose complete directed graph with n vertices into n edge-disjoint cycles with length n−1

Question

I want to know how to decompose a complete directed graph with $n$ nodes into $n$ edge-disjoint cycles with length $n-1$. I found this result was proved in Bermond and Faber - Decomposition of the complete directed graph into k-circuits (Theorem 3). However, the proof is kind of difficult for me to understand, especially the construction seems ambiguous to me. Also, I am wondering whether this observation is true: there exists a decomposition such that all cycles (each expressed as a $1\times(n-1) $ vector and with appropriate shifting) can be written as a $n\times(n-1)$ matrix such that there is no repeated elements in each column. For example, when $n=4$, we consider the matrix $\begin{bmatrix}2&3&4\\1&4&3\\4&1&2\\3&2&1\end{bmatrix}$, in which each column does not have repeated elements, and each row represents a cycle (e.g., the first row is $2\rightarrow 3\rightarrow 4\rightarrow 2$), it can be verified that all cycles are disjoint.

Answer 1

The problem of decomposing the complete directed graph on $n$ vertices into directed cycles of length $m$ was completely settled in Alspach, Gavlas, Sajna, and Verrall, Cycle decompositions IV: complete directed graphs and fixed length directed cycles, Journal of Combinatorial Theory, Series A, 103 (2003) 165-208, available at https://core.ac.uk/download/pdf/81154598.pdf The main result is

1.1. Theorem. For positive integers $m$ and $n$, with $2\le m\le n$, the digraph $K=K_n^*$ can be decomposed into directed cycles of length $m$ if and only if $m$ divides the number of arcs in $K$ and $(m,n)\ne(4,4),(6,3),(6,6)$.

In the special case that concerns us here, the case $m=n-1$, we have,

Lemma 5.7. For each odd integer $m\ge5$, the complete directed graph $K_{m+1}^*$ can be decomposed into directed $m$-cycles.

[Note that we already have the case $m=3$, so this settles in the affirmative the case $m$ odd.]

While the paper is long and difficult, the proof of Lemma 5.7 is less than half a page, and doesn't look too bad (although it does rely on notation defined on previous pages). I encourage you to try to work through it in the case $m=5$, $n=6$.

The paper says the case $m$ odd, $n$ even is the hardest case, so maybe the case where $m=n-1$ is even can also be handled without too much trouble.

Answer 2

In order to get the highly symmetric pattern you and @GerryMyerson have observed, consider the $n$-cycle permutation $\sigma$ of $\{1,2,\dots,n\}$ defined by $$\begin{array}{c} 1 \quad\to\quad 2\!\to\!4\!\to\!6\to\!\cdots\!\to (4m) \quad\to\quad (4m\!-\!1)\\ (4m\!-\!1\!)\to\!(4m\!-\!3)\!\to\!\cdots\!\to\!(2m\!+\!1) \;\to\; (4m\!+\!1) \;\to\; (2m\!-\!1)\!\to\!(2m\!-\!3)\!\to\!\cdots\!\to\!1 \end{array}$$ when $n=4m+1$, and $$\begin{array}{c} 1 \quad\to\quad 2\!\to\!4\!\to\!6\to\!\cdots\!\to (4m+2) \quad\to\quad (4m\!+\!1)\\ (4m\!+\!1\!)\!\to\!(4m\!-\!1)\!\to\!\cdots\!\to\!(2m\!+\!3) \;\to\; (4m\!+\!3) \;\to\; (2m\!+\!1)\!\to\!(2m\!-\!1)\!\to\!\cdots\!\to\!1 \end{array}$$ when $n=4m+3$.

For small $n$ it is :

$$\begin{array}{rrlcrrr} 4\times 0+3,\quad&1 \;\to& 2 &\to&&3\;\to&\!1\\ 4\times 1+1,\quad&1 \;\to& 2\!\to\! 4 &\to&3 \;\to&5\;\to&\! 1\\ 4\times 1+3,\quad&1 \;\to& 2\!\to\! 4\!\to\! 6 &\to&5 \;\to&7\;\to&\! 3\!\to\! 1\\ 4\times 2+1,\quad&1 \;\to& 2\!\to\! 4\!\to\! 6\!\to\! 8 &\to&7\!\to\! 5 \;\to&9\;\to&\! 3\!\to\! 1\\ 4\times 2+3,\quad&1 \;\to& 2\!\to\! 4\!\to\! 6\!\to\! 8\!\to\! 10 &\to&9\!\to\! 7 \;\to&\!\!\!11\;\to&\!\!5\!\to\! 3\!\to\! 1\\ 4\times 3+1,\quad&1 \;\to& 2\!\to\! 4\!\to\! 6\!\to\! 8\!\to\! 10\!\to\! 12&\to&11\to9\!\to\! 7 \;\to&\!\!\!13\;\to&\!\!5\!\to\! 3\!\to\! 1 \end{array}$$

In two-line notation it is :

$$n = 3 = 4\times 0+3,\qquad\sigma=\begin{pmatrix} 1&2&3\\ 2&3&1 \end{pmatrix}$$

$$n = 5 = 4\times 1+1,\qquad\sigma=\begin{pmatrix} 1&2&3&4&5\\ 2&4&5&3&1 \end{pmatrix}$$

$$n = 7 = 4\times 1+3,\qquad\sigma=\begin{pmatrix} 1&2&3&4&5&6&7\\ 2&4&1&6&7&5&3 \end{pmatrix}$$

$$n = 9 = 4\times 2+1,\qquad\sigma=\begin{pmatrix} 1&2&3&4&5&6&7&8&9\\ 2&4&1&6&9&8&5&7&3 \end{pmatrix}$$

$$n = 11 = 4\times 2+3,\qquad\sigma=\begin{pmatrix} 1&2&3&4&5&6&7&8&9&10&11\\ 2&4&1&6&3&8&11&10&7&9&5 \end{pmatrix}$$

$$n = 13 = 4\times 3+1,\qquad\sigma=\begin{pmatrix} 1&2&3&4&5&6&7&8&9&10&11&12&13\\ 2&4&1&6&3&8&13&10&7&12&9&11&5 \end{pmatrix}$$

Now write the $n$ iterations $\text{Id}, \sigma, \sigma^2, \dots, \sigma^{n-1}$ of $\sigma$ in one-line notation, stack them as $n$ rows, sort the rows in lexical order, and ignore the last column -- I've greyed it out below. The $n\times n$ matrix then starts with the two-line notation above :

$n = 3 = 4\times 0+3,$ $$\begin{array}{r} \color{grey}{\sigma^0}\\ \color{grey}{\sigma^1}\\ \color{grey}{\sigma^2} \end{array}\begin{pmatrix} 1&2&\color{grey}{3}\\ 2&3&\color{grey}{1}\\ 3&1&\color{grey}{2} \end{pmatrix}$$

$n = 5 = 4\times 1+1,$ $$\begin{array}{r} \color{grey}{\sigma^0}\\ \color{grey}{\sigma^1}\\ \color{grey}{\sigma^3}\\ \color{grey}{\sigma^2}\\ \color{grey}{\sigma^4} \end{array} \begin{pmatrix} 1&2&3&4&\color{grey}{5}\\ 2&4&5&3&\color{grey}{1}\\ 3&5&2&1&\color{grey}{4}\\ 4&3&1&5&\color{grey}{2}\\ 5&1&4&2&\color{grey}{3} \end{pmatrix}$$

$n = 7 = 4\times 1+3,$ $$\begin{array}{r} \color{grey}{\sigma^0}\\ \color{grey}{\sigma^1}\\ \color{grey}{\sigma^6}\\ \color{grey}{\sigma^2}\\ \color{grey}{\sigma^4}\\ \color{grey}{\sigma^3}\\ \color{grey}{\sigma^5} \end{array}\begin{pmatrix} 1&2&3&4&5&6&\color{grey}{7}\\ 2&4&1&6&7&5&\color{grey}{3}\\ 3&1&7&2&6&4&\color{grey}{5}\\ 4&6&2&5&3&7&\color{grey}{1}\\ 5&7&6&3&2&1&\color{grey}{4}\\ 6&5&4&7&1&3&\color{grey}{2}\\ 7&3&5&1&4&2&\color{grey}{6} \end{pmatrix}$$

$n = 9 = 4\times 2+1,$ $$\begin{array}{r} \color{grey}{\sigma^0}\\ \color{grey}{\sigma^1}\\ \color{grey}{\sigma^8}\\ \color{grey}{\sigma^2}\\ \color{grey}{\sigma^6}\\ \color{grey}{\sigma^3}\\ \color{grey}{\sigma^5}\\ \color{grey}{\sigma^4}\\ \color{grey}{\sigma^7} \end{array}\begin{pmatrix} 1&2&3&4&5&6&7&8&\color{grey}{9}\\ 2&4&1&6&9&8&5&7&\color{grey}{3}\\ 3&1&9&2&7&4&8&6&\color{grey}{5}\\ 4&6&2&8&3&7&9&5&\color{grey}{1}\\ 5&9&7&3&6&1&4&2&\color{grey}{8}\\ 6&8&4&7&1&5&3&9&\color{grey}{2}\\ 7&5&8&9&4&3&2&1&\color{grey}{6}\\ 8&7&6&5&2&9&1&3&\color{grey}{4}\\ 9&3&5&1&8&2&6&4&\color{grey}{7} \end{pmatrix}$$

$n = 11 = 4\times 2+3,$ $$\color{grey}{\begin{array}{r} \sigma^0\\ \sigma^1\\ \sigma^{10}\\ \sigma^2\\ \sigma^9\\ \sigma^3\\ \sigma^7\\ \sigma^4\\ \sigma^6\\ \sigma^5\\ \sigma^8 \end{array}}\begin{pmatrix} 1&2&3&4&5&6&7&8&9&10&\color{grey}{11}\\ 2&4&1&6&3&8&11&10&7&9&\color{grey}{5}\\ 3&1&5&2&11&4&9&6&10&8&\color{grey}{7}\\ 4&6&2&8&1&10&5&9&11&7&\color{grey}{3}\\ 5&3&11&1&7&2&10&4&8&6&\color{grey}{9}\\ 6&8&4&10&2&9&3&7&5&11&\color{grey}{1}\\ 7&11&9&5&10&3&6&1&4&2&\color{grey}{8}\\ 8&10&6&9&4&7&1&11&3&5&\color{grey}{2}\\ 9&7&10&11&8&5&4&3&2&1&\color{grey}{6}\\ 10&9&8&7&6&11&2&5&1&3&\color{grey}{4}\\ 11&5&7&3&9&1&8&2&6&4&\color{grey}{10} \end{pmatrix}$$

$n = 13 = 4\times 3+1,$ $$\color{grey}{\begin{array}{r} \sigma^0\\ \sigma^1\\ \sigma^{12}\\ \sigma^2\\ \sigma^{11}\\ \sigma^3\\ \sigma^9\\ \sigma^4\\ \sigma^8\\ \sigma^5\\ \sigma^7\\ \sigma^6\\ \sigma^{10} \end{array}}\begin{pmatrix} 1&2&3&4&5&6&7&8&9&10&11&12&\color{grey}{13}\\ 2&4&1&6&3&8&13&10&7&12&9&11&\color{grey}{5}\\ 3&1&5&2&13&4&9&6&11&8&12&10&\color{grey}{7}\\ 4&6&2&8&1&10&5&12&13&11&7&9&\color{grey}{3}\\ 5&3&13&1&7&2&11&4&12&6&10&8&\color{grey}{9}\\ 6&8&4&10&2&12&3&11&5&9&13&7&\color{grey}{1}\\ 7&13&9&5&11&3&10&1&8&2&6&4&\color{grey}{12}\\ 8&10&6&12&4&11&1&9&3&7&5&13&\color{grey}{2}\\ 9&7&11&13&12&5&8&3&6&1&4&2&\color{grey}{10}\\ 10&12&8&11&6&9&2&7&1&13&3&5&\color{grey}{4}\\ 11&9&12&7&10&13&6&5&4&3&2&1&\color{grey}{8}\\ 12&11&10&9&8&7&4&13&2&5&1&3&\color{grey}{6}\\ 13&5&7&3&9&1&12&2&10&4&8&6&\color{grey}{11} \end{pmatrix}$$

I don't know why this works out so symmetyrically and haven't figured it out for $n$ even.