Arbitrary orientations of Hamilton cycles in digraphs

Louis DeBiasio, Daniela Kühn, Theodore Molla, Deryk Osthus, Amelia Taylor

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)
93 Downloads (Pure)

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 languageEnglish
Pages (from-to)1553-1584
Number of pages32
JournalSIAM Journal on Discrete Mathematics
Volume29
Issue number3
DOIs
Publication statusPublished - 2015

Keywords

  • Digraphs
  • Extremal problems
  • Hamilton cycles
  • Robust expanders

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Arbitrary orientations of Hamilton cycles in digraphs'. Together they form a unique fingerprint.

Cite this