Degree sequences forcing Hamilton cycles in directed graphs

Daniela Kühn; Deryk Osthus; Andrew Treglown

doi:10.1016/j.endm.2009.07.057

Degree sequences forcing Hamilton cycles in directed graphs

Daniela Kühn^*, Deryk Osthus, Andrew Treglown

^*Corresponding author for this work

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

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 d_i^- ≥ i + o (n) and d_i⁺ ≥ 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 language	English
Pages (from-to)	347-351
Number of pages	5
Journal	Electronic Notes in Discrete Mathematics
Volume	34
DOIs	https://doi.org/10.1016/j.endm.2009.07.057
Publication status	Published - 1 Aug 2009

Keywords

degree sequences
directed graphs
Hamilton cycles

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.endm.2009.07.057

Cite this

@article{f39d828ee7aa484c95d932cd52d09e5a,

title = "Degree sequences forcing Hamilton cycles in directed graphs",

abstract = "We prove the following approximate version of P{\'o}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{\'a}tal's theorem for digraphs. This asymptotically confirms conjectures of Nash-Williams from 1968 and 1975.",

keywords = "degree sequences, directed graphs, Hamilton cycles",

author = "Daniela K{\"u}hn and Deryk Osthus and Andrew Treglown",

year = "2009",

month = aug,

day = "1",

doi = "10.1016/j.endm.2009.07.057",

language = "English",

volume = "34",

pages = "347--351",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

}

TY - JOUR

T1 - Degree sequences forcing Hamilton cycles in directed graphs

AU - Kühn, Daniela

AU - Osthus, Deryk

AU - Treglown, Andrew

PY - 2009/8/1

Y1 - 2009/8/1

N2 - 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.

AB - 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.

KW - degree sequences

KW - directed graphs

KW - Hamilton cycles

UR - http://www.scopus.com/inward/record.url?scp=67651146512&partnerID=8YFLogxK

U2 - 10.1016/j.endm.2009.07.057

DO - 10.1016/j.endm.2009.07.057

M3 - Article

AN - SCOPUS:67651146512

SN - 1571-0653

VL - 34

SP - 347

EP - 351

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

Degree sequences forcing Hamilton cycles in directed graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this