Projects per year
Abstract
We show that for each beta > 0, every digraph G of sufficiently large order n whose outdegree and indegree sequences d(1)(+) = min {i + beta n, n/2} is Hamiltonian. In fact, we can weaken these assumptions to (i) d(1)(+) >= min {i + beta n, n/2} or d(nibeta n)() >= n  i, (ii) d(1)() >= min {i + beta n, n/2} or d(nibeta n)() >= n  i, and still deduce that G is Hamiltonian. This provides an approximate version of a conjecture of NashWilliams from 1975 and improves a previous result of Kuhn, Osthus, and Treglown.
Original language  English 

Pages (fromto)  709756 
Number of pages  48 
Journal  SIAM Journal on Discrete Mathematics 
Volume  24 
Issue number  3 
DOIs  
Publication status  Published  1 Jan 2010 
Keywords
 directed graphs
 Hamilton cycles
 extremal problems
 regularity lemma
Fingerprint
Dive into the research topics of 'A Semiexact Degree Condition for Hamilton Cycles in Digraphs'. Together they form a unique fingerprint.Projects
 2 Finished

Directed graphs and the regularity method
Engineering & Physical Science Research Council
1/10/07 → 31/03/11
Project: Research Councils

Graph expansion and applications
Engineering & Physical Science Research Council
1/08/07 → 30/11/09
Project: Research Councils