Cycle Decompositions of Complete Digraphs
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.