A Dirac-Type Result on Hamilton Cycles in Oriented Graphs

Research output: Contribution to journalArticle

Authors

Colleges, School and Institutes

Abstract

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 [21]. 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 [10]. We also prove an Ore-type theorem for oriented graphs.

Details

Original languageEnglish
JournalCombinatorics, Probability and Computing
Volume17
Issue number05
Early online date4 Jul 2008
Publication statusPublished - 1 Sep 2008