![](/files/happy5.png)
Hamilton cycle in small d-diregular graphs
An directed graph is -diregular if every vertex has indegree and outdegree at least
.
Conjecture For
, every
-diregular oriented graph on at most
vertices has a Hamilton cycle.
![$ d >2 $](/files/tex/6b29cd29e21416ff46f4898a33bcc7355436ee8f.png)
![$ d $](/files/tex/aeba4a4076fc495e8b5df04d874f2911a838883a.png)
![$ 4d+1 $](/files/tex/5d467147b18bddde059e7178ebf5bcf6c4b4f516.png)
The disjoint union of two regular tournaments on vertices shows that this would be best possible. For
-diregular oriented graphs with an arbitrary order of vertices, Jackson conjectured the existence of a long cycle.
Kühn and Osthus [KO] conjectured that it may actually be possible to increase the size of the graph even further if we assume that the graph is strongly 2-connected.
Problem Is it true that for each
, every
-regular strongly
-connected oriented graph
on at most
vertices has a Hamilton cycle?
![$ d >2 $](/files/tex/6b29cd29e21416ff46f4898a33bcc7355436ee8f.png)
![$ d $](/files/tex/aeba4a4076fc495e8b5df04d874f2911a838883a.png)
![$ 2 $](/files/tex/5271e36bb1c040e0f14061d89cd97d0c86d4e06f.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ 6d $](/files/tex/37851de5d7a7a2a499b168ae71a115fdac720b6c.png)
Bibliography
*[J] B. Jackson. Long paths and cycles in oriented graphs, J. Graph Theory 5 (1981), 145-157.
[KO] D. Osthus and D. Kühn, A survey on Hamilton cycles in directed graphs, European J. Combinatorics 33 (2012), 750-766.
* indicates original appearance(s) of problem.