Cycle decompositions of complete digraphs (Q2227833)

Summary: In this paper, we consider the problem of decomposing the complete directed graph \(K_n^\ast\) into cycles of given lengths. We consider general necessary conditions for a directed cycle decomposition of \(K_n^\ast\) 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 \pmod 4\), \(K_n^\ast\) is not decomposable.