A Dirac-Type Result on Hamilton Cycles in Oriented Graphs
Research output: Contribution to journal › Article
Colleges, School and Institutes
We show that for each alpha > 0 every sufficiently large oriented graph G with delta(+)(G),delta(-)(G) >= 3\G\/8 + alpha\G\ contains a Hamilton cycle. This gives an approximate solution to a problem of Thomassen . In fact,we prove the stronger result that G is still Hamiltonian if delta(G) + delta(+)(G) + delta(-)(G) >= 3\G\/2 + alpha\G\. Up to the term alpha\G\, this confirms a conjecture of Haggkvist . We also prove an Ore-type theorem for oriented graphs.
|Journal||Combinatorics, Probability and Computing|
|Early online date||4 Jul 2008|
|Publication status||Published - 1 Sep 2008|