Powers of Hamilton cycles in oriented and directed graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914065458135040 |
|---|---|
| author | DeBiasio, Louis Han, Jie Lo, Allan Molla, Theodore Piga, Simón Treglown, Andrew |
| author_facet | DeBiasio, Louis Han, Jie Lo, Allan Molla, Theodore Piga, Simón Treglown, Andrew |
| contents | The Pósa--Seymour conjecture determines the minimum degree threshold for forcing the $k$th power of a Hamilton cycle in a graph. After numerous partial results, Komlós, Sárközy and Szemerédi proved the conjecture for sufficiently large graphs. In this paper we focus on the analogous problem for digraphs and for oriented graphs. We asymptotically determine the minimum total degree threshold for forcing the square of a Hamilton cycle in a digraph. We also give a conjecture on the corresponding threshold for $k$th powers of a Hamilton cycle more generally. For oriented graphs, we provide a minimum semi-degree condition that forces the $k$th power of a Hamilton cycle; although this minimum semi-degree condition is not tight, it does provide the correct order of magnitude of the threshold. Turán-type problems for oriented graphs are also discussed. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_18336 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Powers of Hamilton cycles in oriented and directed graphs DeBiasio, Louis Han, Jie Lo, Allan Molla, Theodore Piga, Simón Treglown, Andrew Combinatorics The Pósa--Seymour conjecture determines the minimum degree threshold for forcing the $k$th power of a Hamilton cycle in a graph. After numerous partial results, Komlós, Sárközy and Szemerédi proved the conjecture for sufficiently large graphs. In this paper we focus on the analogous problem for digraphs and for oriented graphs. We asymptotically determine the minimum total degree threshold for forcing the square of a Hamilton cycle in a digraph. We also give a conjecture on the corresponding threshold for $k$th powers of a Hamilton cycle more generally. For oriented graphs, we provide a minimum semi-degree condition that forces the $k$th power of a Hamilton cycle; although this minimum semi-degree condition is not tight, it does provide the correct order of magnitude of the threshold. Turán-type problems for oriented graphs are also discussed. |
| title | Powers of Hamilton cycles in oriented and directed graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2412.18336 |