Arbitrary orientations of Hamilton cycles in directed graphs of large minimum degree

In 1960, Ghouila-Houri proved that every strongly connected directed graph G on n vertices with minimum degree at least n contains a directed Hamilton cycle. We asymptotically generalize this result by proving the following: every directed graph G on n vertices with minimum degree at least ( 1 + o ( 1 ) ) n contains every orientation of a Hamilton cycle, except for the directed Hamilton cycle in the case when G is not strongly connected. In fact, this minimum degree condition forces every orientation of a cycle in G of every possible length, other than perhaps the directed cycles.

Authors

Institutions

Publication Details

Journal
Journal of Combinatorial Theory Series B
Published
2026-11-09
DOI
https://doi.org/10.1016/j.jctb.2026.10.004
Citations
3
Primary Topic
Limits and Structures in Graph Theory
Type
article
Field-Weighted Citation Impact
3.82

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Arbitrary orientations of Hamilton cycles in directed graphs of large minimum degree

Louis DeBiasio, Andrew Treglown
3 citations
Journal of Combinatorial Theory Series B
Limits and Structures in Graph Theory
3.82
article

Arbitrary orientations of Hamilton cycles in directed graphs of large minimum degree

Louis DeBiasio, Andrew Treglown
article en
3 citations

Abstract

In 1960, Ghouila-Houri proved that every strongly connected directed graph G on n vertices with minimum degree at least n contains a directed Hamilton cycle. We asymptotically generalize this result by proving the following: every directed graph G on n vertices with minimum degree at least ( 1 + o ( 1 ) ) n contains every orientation of a Hamilton cycle, except for the directed Hamilton cycle in the case when G is not strongly connected. In fact, this minimum degree condition forces every orientation of a cycle in G of every possible length, other than perhaps the directed cycles.

Journal of Combinatorial Theory Series BVol. 183
University of Birmingham (GB), Miami University (US)
National Science Foundation, Engineering and Physical Sciences Research Council
Openalex Percentile: Top 11%
Limits and Structures in Graph Theory
3.82
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon