Arbitrary orientations of Hamilton cycles in digraphs

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

doi:10.1137/140974675

Arbitrary orientations of Hamilton cycles in digraphs

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

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

148 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 language	English
Pages (from-to)	1553-1584
Number of pages	32
Journal	SIAM Journal on Discrete Mathematics
Volume	29
Issue number	3
DOIs	https://doi.org/10.1137/140974675
Publication status	Published - 2015

Keywords

Digraphs
Extremal problems
Hamilton cycles
Robust expanders

ASJC Scopus subject areas

General Mathematics

Access to Document

10.1137/140974675

Kuhn_Arbitrary_orientations_SIAM_J_Discrete_Math_2015
Eligibility for repository: Checked on 11/1/2016
Final published version, 580 KBLicence: Creative Commons: Attribution (CC BY)

Cite this

@article{b935ef704239435bbe65ae22bfb2ebdf,

title = "Arbitrary orientations of Hamilton cycles in digraphs",

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{\^A}aggkvist and Thomason.",

keywords = "Digraphs, Extremal problems, Hamilton cycles, Robust expanders",

author = "Louis DeBiasio and Daniela K{\"u}hn and Theodore Molla and Deryk Osthus and Amelia Taylor",

year = "2015",

doi = "10.1137/140974675",

language = "English",

volume = "29",

pages = "1553--1584",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - Arbitrary orientations of Hamilton cycles in digraphs

AU - DeBiasio, Louis

AU - Kühn, Daniela

AU - Molla, Theodore

AU - Osthus, Deryk

AU - Taylor, Amelia

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - Digraphs

KW - Extremal problems

KW - Hamilton cycles

KW - Robust expanders

UR - http://www.scopus.com/inward/record.url?scp=84943154419&partnerID=8YFLogxK

U2 - 10.1137/140974675

DO - 10.1137/140974675

M3 - Article

AN - SCOPUS:84943154419

SN - 0895-4801

VL - 29

SP - 1553

EP - 1584

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 3

ER -

Arbitrary orientations of Hamilton cycles in digraphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this