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
- Louis DeBiasio (ORCID: https://orcid.org/0000-0002-7569-7952)
- Andrew Treglown (ORCID: https://orcid.org/0000-0002-4293-5678)
Institutions
- University of Birmingham (GB)
- Miami University (US)
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
- National Science Foundation
- Engineering and Physical Sciences Research Council