Hamiltonian degree sequences in digraphs

Research output: Contribution to journalArticlepeer-review

31 Citations (Scopus)


We show that for each n > 0 every digraph G of sufficiently large order n is Hamiltonian if its out- and indegree sequences d(1)(+) = i + eta n or d(n-i-eta n)(-) >= n - i and (ii) d(i)(-) >= i + eta n or d(n-i-eta n)(+) >= n - i for all i <n/2. This gives an approximate solution to a problem of Nash-Williams (1975) [22] concerning a digraph analogue of Chvatal's theorem. In fact, we prove the stronger result that such digraphs G are pancyclic. (C) 2009 Elsevier Inc. All rights reserved.
Original languageEnglish
Pages (from-to)367-380
Number of pages14
JournalJournal of Combinatorial Theory. Series B
Issue number4
Publication statusPublished - 1 Jul 2010


  • Directed graphs
  • Hamilton cycles
  • Tournaments
  • Regularity lemma
  • Expansion


Dive into the research topics of 'Hamiltonian degree sequences in digraphs'. Together they form a unique fingerprint.

Cite this