Arbitrary orientations of Hamilton cycles in digraphs

DOI10.1137/140974675MaRDI QIDQ2944460zbMATH OpenOpenAlexFDO

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

Publication date 2 September 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.1812

zbMATH Keywords

digraphsextremal problemsHamilton cyclesrobust expanders

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

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.

Recommendations

• scientific article; zbMATH DE number 1047732
• Orientations of hamiltonian cycles in large digraphs
• Oriented hamilton cycles in digraphs
• Arbitrary orientations of Hamilton cycles in oriented graphs
• A Dirac-Type Result on Hamilton Cycles in Oriented Graphs

Cites work

• A counterexample to a conjecture of Grant
• A survey on Hamilton cycles in directed graphs
• An exact minimum degree condition for Hamilton cycles in oriented graphs
• Arbitrary orientations of Hamilton cycles in oriented graphs
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• scientific article; zbMATH DE number 3149611 (Why is no real title available?)
• scientific article; zbMATH DE number 3700874 (Why is no real title available?)
• scientific article; zbMATH DE number 1047732 (Why is no real title available?)
• On Hamiltonian bipartite graphs
• Oriented hamilton cycles in digraphs
• Paths and Cycles in Tournaments
• Semi-degree threshold for anti-directed Hamiltonian cycles
• Some Theorems on Abstract Graphs

Cited in

(23)

• Orientations of Hamiltonian cycles in bipartite digraphs
• Hamiltonian numbers in oriented graphs
• Spanning trees of dense directed graphs
• Vertex-oriented Hamilton cycles in directed graphs
• Hamiltonicity of digraphs for universal cycles of permutations
• Spanning trees in dense directed graphs
• On the Dirac-type conjecture for anti-directed Hamiltonian digraphs
• 4-cycles in mixing digraphs
• Orientations of hamiltonian cycles in large digraphs
• scientific article; zbMATH DE number 1047732 (Why is no real title available?)
• scientific article; zbMATH DE number 1154589 (Why is no real title available?)
• Oriented hamilton cycles in digraphs
• Orientation Ramsey thresholds for cycles and cliques
• Packing and counting arbitrary Hamilton cycles in random digraphs
• Oriented discrepancy of Hamilton cycles
• Arbitrary orientations of Hamilton cycles in oriented graphs
• An oriented discrepancy version of Dirac's theorem
• On oriented cycles in randomly perturbed digraphs
• Spanning subdivisions in dense digraphs
• A note between transitive C₄-factor and oriented Ramsey number
• Cycles of every length and orientation in randomly perturbed digraphs (extended abstract)
• Randomly perturbed digraphs also have bounded-degree spanning trees
• Semi-degree threshold for anti-directed Hamiltonian cycles

This page was built for publication: Arbitrary orientations of Hamilton cycles in digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2944460)