Hamilton cycles in dense regular digraphs and oriented graphs

Allan Lo; Viresh Patel; Mehmet Akif  Yildiz

doi:10.1016/j.jctb.2023.09.004

Hamilton cycles in dense regular digraphs and oriented graphs

Allan Lo, Viresh Patel, Mehmet Akif Yildiz^*

^*Corresponding author for this work

Mathematics

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

15 Downloads (Pure)

Abstract

We prove that for every ε>0 there exists n₀=n₀(ε) such that every regular oriented graph on n>n₀ vertices and degree at least (1/4+ε)n has a Hamilton cycle. This establishes an approximate version of a conjecture of Jackson from 1981. We also establish a result related to a conjecture of Kühn and Osthus about the Hamiltonicity of regular directed graphs with suitable degree and connectivity conditions.

Original language	English
Pages (from-to)	119-160
Number of pages	42
Journal	Journal of Combinatorial Theory. Series B
Volume	164
Early online date	4 Oct 2023
DOIs	https://doi.org/10.1016/j.jctb.2023.09.004
Publication status	Published - Jan 2024

Access to Document

10.1016/j.jctb.2023.09.004Licence: Creative Commons: Attribution (CC BY)

LoA2023HamiltonFinal published version, 765 KBLicence: Creative Commons: Attribution (CC BY)

1 Finished
1 Active

Ramsey theory: an extremal perspective
Treglown, A. & Lo, A.
Engineering & Physical Science Research Council
1/01/22 → 31/12/24
Project: Research Councils
Matchings and tilings in graphs
Lo, A. & Treglown, A.
Engineering & Physical Science Research Council
1/03/21 → 29/02/24
Project: Research Councils

Cite this

@article{5d8c44bf080a44f99b119b0ff836e79b,

title = "Hamilton cycles in dense regular digraphs and oriented graphs",

abstract = "We prove that for every ε>0 there exists n0=n0(ε) such that every regular oriented graph on n>n0 vertices and degree at least (1/4+ε)n has a Hamilton cycle. This establishes an approximate version of a conjecture of Jackson from 1981. We also establish a result related to a conjecture of K{\"u}hn and Osthus about the Hamiltonicity of regular directed graphs with suitable degree and connectivity conditions. ",

author = "Allan Lo and Viresh Patel and Yildiz, {Mehmet Akif}",

year = "2024",

month = jan,

doi = "10.1016/j.jctb.2023.09.004",

language = "English",

volume = "164",

pages = "119--160",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Elsevier",

}

TY - JOUR

T1 - Hamilton cycles in dense regular digraphs and oriented graphs

AU - Lo, Allan

AU - Patel, Viresh

AU - Yildiz, Mehmet Akif

PY - 2024/1

Y1 - 2024/1

N2 - We prove that for every ε>0 there exists n0=n0(ε) such that every regular oriented graph on n>n0 vertices and degree at least (1/4+ε)n has a Hamilton cycle. This establishes an approximate version of a conjecture of Jackson from 1981. We also establish a result related to a conjecture of Kühn and Osthus about the Hamiltonicity of regular directed graphs with suitable degree and connectivity conditions.

AB - We prove that for every ε>0 there exists n0=n0(ε) such that every regular oriented graph on n>n0 vertices and degree at least (1/4+ε)n has a Hamilton cycle. This establishes an approximate version of a conjecture of Jackson from 1981. We also establish a result related to a conjecture of Kühn and Osthus about the Hamiltonicity of regular directed graphs with suitable degree and connectivity conditions.

UR - https://arxiv.org/abs/2203.10112

U2 - 10.1016/j.jctb.2023.09.004

DO - 10.1016/j.jctb.2023.09.004

M3 - Article

SN - 0095-8956

VL - 164

SP - 119

EP - 160

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Hamilton cycles in dense regular digraphs and oriented graphs

Abstract

Access to Document

Fingerprint

Projects

Ramsey theory: an extremal perspective

Matchings and tilings in graphs

Cite this