Arbitrary orientations of Hamilton cycles in directed graphs of large minimum degree
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918021297078272 |
|---|---|
| author | DeBiasio, Louis Treglown, Andrew |
| author_facet | DeBiasio, Louis Treglown, Andrew |
| contents | 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 and 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_09793 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Arbitrary orientations of Hamilton cycles in directed graphs of large minimum degree DeBiasio, Louis Treglown, Andrew Combinatorics 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 and 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. |
| title | Arbitrary orientations of Hamilton cycles in directed graphs of large minimum degree |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2505.09793 |