Arbitrary orientations of cycles in oriented graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909978367885312 |
|---|---|
| author | Wang, Guanghui Wang, Yun Zhang, Zhiwei |
| author_facet | Wang, Guanghui Wang, Yun Zhang, Zhiwei |
| contents | We show that every sufficiently large oriented graph $G$ with minimum indegree and outdegree both at least $(3|V(G)|-1)/8$ contains every orientation of a Hamilton cycle. This result improves the approximate bound established by Kelly and resolves a long-standing problem posed by Häggkvist and Thomason in 1995. The degree condition is tight and it can be improved to $(3|V(G)|-4)/8$ for Hamilton cycles that are nearly directed, generalizing a classic result by Keevash, Kühn and Osthus. Additionally, we derive a pancyclicity result for arbitrary orientations. More precisely, the above degree condition suffices to guarantee the existence of cycles of every possible orientation and every possible length unless $G$ is isomorphic to one of the exceptional oriented graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_09794 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Arbitrary orientations of cycles in oriented graphs Wang, Guanghui Wang, Yun Zhang, Zhiwei Combinatorics 05C20, 05C45, 05C38, 05C35 We show that every sufficiently large oriented graph $G$ with minimum indegree and outdegree both at least $(3|V(G)|-1)/8$ contains every orientation of a Hamilton cycle. This result improves the approximate bound established by Kelly and resolves a long-standing problem posed by Häggkvist and Thomason in 1995. The degree condition is tight and it can be improved to $(3|V(G)|-4)/8$ for Hamilton cycles that are nearly directed, generalizing a classic result by Keevash, Kühn and Osthus. Additionally, we derive a pancyclicity result for arbitrary orientations. More precisely, the above degree condition suffices to guarantee the existence of cycles of every possible orientation and every possible length unless $G$ is isomorphic to one of the exceptional oriented graphs. |
| title | Arbitrary orientations of cycles in oriented graphs |
| topic | Combinatorics 05C20, 05C45, 05C38, 05C35 |
| url | https://arxiv.org/abs/2504.09794 |