Cycle Decompositions of Complete Digraphs

Abstract

In this paper, we consider the problem of decomposing the complete directed graph $K_n^*$ into cycles of given lengths.  We consider general necessary conditions for a directed cycle decomposition of $K_n^*$ into $t$ cycles of lengths $m_1, m_2, \ldots, m_t$  to exist and and provide a powerful construction for creating such decompositions in the case where there is one 'large' cycle. Finally, we give a complete solution in the case when there are exactly three cycles of lengths $\alpha, \beta, \gamma \neq 2$. Somewhat surprisingly, the general necessary conditions turn out not to be sufficient in this case.  In particular, when $\gamma=n$, $\alpha+\beta > n+2$ and $\alpha+\beta \equiv n$ (mod 4), $K_n^*$ is not decomposable.