Degree sequences forcing Hamilton cycles in directed graphs

Daniela Kühn*, Deryk Osthus, Andrew Treglown

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


We prove the following approximate version of Pósa's theorem for directed graphs: every directed graph on n vertices whose in- and outdegree sequences satisfy di- ≥ i + o (n) and di+ ≥ i + o (n) for all i ≤ n / 2 has a Hamilton cycle. In fact, we prove that such digraphs are pancyclic (i.e. contain cycles of lengths 2, ..., n). We also prove an approximate version of Chvátal's theorem for digraphs. This asymptotically confirms conjectures of Nash-Williams from 1968 and 1975.

Original languageEnglish
Pages (from-to)347-351
Number of pages5
JournalElectronic Notes in Discrete Mathematics
Publication statusPublished - 1 Aug 2009


  • degree sequences
  • directed graphs
  • Hamilton cycles

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Degree sequences forcing Hamilton cycles in directed graphs'. Together they form a unique fingerprint.

Cite this