![](/files/happy5.png)
Conjecture If
is a
-regular directed graph with no parallel arcs, then
contains a collection of
arc-disjoint directed cycles.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ {k+1 \choose 2} $](/files/tex/783a85f7ae121a116b289d0f5b090f98fc9f959e.png)
If true, would be best possible as shown by the complete symmetric digraph.
Alon et al. [AMM] showed that a -regular directed graph with no parallel arcs contains at least
arc-disjoint directed cycles. It was then improved by Alon [A] who showed that every directed graph with minimum outdegree at least
contains at least
arc-disjoint directed cycles.
Bibliography
[A} N. Alon, Disjoint directed cycles, J. Combinatorial Theory, Ser. B, 68 (1996), 167-178.
*[AMM] N. Alon, C. McDiarmid and M. Molloy, Edge-disjoint cycles in regular directed graphs, J. Graph Theory, 22 (1996), no. 3, 231-237.
* indicates original appearance(s) of problem.