Abstract
Let n be sufficiently large and suppose that G is a digraph on n vertices where every vertex has in- and outdegree at least n/2. We show that G contains every orientation of a Hamilton cycle except, possibly, the antidirected one. The antidirected case was settled by DeBiasio and Molla, where the threshold is n/2 + 1. Our result is best possible and improves on an approximate result by HÂaggkvist and Thomason.
| Original language | English |
|---|---|
| Pages (from-to) | 1553-1584 |
| Number of pages | 32 |
| Journal | SIAM Journal on Discrete Mathematics |
| Volume | 29 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - 2015 |
Keywords
- Digraphs
- Extremal problems
- Hamilton cycles
- Robust expanders
ASJC Scopus subject areas
- General Mathematics
Fingerprint
Dive into the research topics of 'Arbitrary orientations of Hamilton cycles in digraphs'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver