Home » Subject » Graph Theory » Directed Graphs
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

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options