Home » Subject » Graph Theory » Directed Graphs

Hamilton cycle in small d-diregular graphs

Importance: Medium ✭✭
Author(s): Jackson, Bill
Subject: Graph Theory
» Directed Graphs
Keywords:
Recomm. for undergrads: no
Posted by: fhavet
on: March 8th, 2013

An directed graph is $ k $-diregular if every vertex has indegree and outdegree at least $ k $.

Conjecture   For $ d >2 $, every $ d $-diregular oriented graph on at most $ 4d+1 $ vertices has a Hamilton cycle.

The disjoint union of two regular tournaments on $ 2d+1 $ vertices shows that this would be best possible. For $ d $-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 $ d >2 $, every $ d $-regular strongly $ 2 $-connected oriented graph $ G $ on at most $ 6d $ vertices has a Hamilton cycle?

Related problems

Long directed cycles in diregular digraphs

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.
add new comment