Home » Subject » Graph Theory » Directed Graphs

Long directed cycles in diregular digraphs

Importance: High ✭✭✭
Author(s): Jackson, Bill
Subject: Graph Theory
» Directed Graphs
Keywords:
Recomm. for undergrads: no
Posted by: fhavet
on: March 1st, 2013
Conjecture   Every strong oriented graph in which each vertex has indegree and outdegree at least $ d $ contains a directed cycle of length at least $ 2d+1 $.

The disjoint union of two regular tournaments on $ 2d+1 $ vertices shows that this would be best possible.

If the oriented graph has order at most $ 4d+1 $, Jackson conjecture the existence of a longer cycle, namely a Hamilton cycle

Related problems

Directed path of length twice the minimum outdegree
Hamilton cycle in small d-diregular graphs

Bibliography

*[J] B. Jackson. Long paths and cycles in oriented graphs. J. Graph Theory 5 (1981), 145--157.


* indicates original appearance(s) of problem.
add new comment