×

Arbitrary orientations of Hamilton cycles in digraphs. (English) Zbl 1320.05049

Summary: 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 L. DeBiasio and T. Molla [“Semi-degree threshold for anti-directed Hamilton cycles”, Preprint, arXiv:1308.0269], where the threshold is \(n/2+1\). Our result is best possible and improves on an approximate result by R. Häggkvist and A. Thomason [J. Graph Theory 19, No. 4, 471–479 (1995; Zbl 0833.05037)].

MSC:

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

Citations:

Zbl 0833.05037
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] M. C. Cai, {\it A counterexample to a conjecture of Grant}, Discrete Math., 44 (1983), p. 111. · Zbl 0502.05028
[2] L. DeBiasio and T. Molla, {\it Semi-Degree Threshold for Anti-Directed Hamilton Cycles}, preprint, arXiv:1308.0269, 2013. · Zbl 1329.05127
[3] G. A. Dirac, {\it Some theorems on abstract graphs}, Proc. London Math. Soc., 2 (1952), pp. 69-81. · Zbl 0047.17001
[4] A. Ghouila-Houri, {\it Une condition suffisante d’existence d’un circuit Hamiltonien}, C.R. Acad. Sci. Paris, 25 (1960), pp. 495-497. · Zbl 0091.37503
[5] D. Grant, {\it Antidirected Hamilton cycles in digraphs}, Ars Combin., 10 (1980), pp. 205-209. · Zbl 0448.05034
[6] R. Häggkvist and A. Thomason, {\it Oriented Hamilton cycles in oriented graphs}, in Combinatorics, Geometry and Probability, Cambridge University Press, Cambridge, UK, 1997, pp. 339-353. · Zbl 0879.05045
[7] R. Häggkvist and A. Thomason, {\it Oriented Hamilton cycles in digraphs}, J. Graph Theory, 20 (1995), pp. 471-479. · Zbl 0833.05037
[8] P. Keevash, D. Kühn, and D. Osthus, {\it An exact minimum degree condition for Hamilton cycles in oriented graphs}, J. London Math. Soc., 79 (2009), pp. 144-166. · Zbl 1198.05081
[9] L. Kelly, {\it Arbitrary orientations of Hamilton cycles in oriented graphs}, Electron. J. Combin., 18 (2011). · Zbl 1236.05120
[10] D. Kühn and D. Osthus, {\it A survey on Hamilton cycles in directed graphs}, European J. Combin., 33 (2012), pp. 750-766. · Zbl 1239.05114
[11] D. Kühn and D. Osthus, {\it Hamilton decompositions of regular expanders: A proof of Kelly’s conjecture for large tournaments}, Adv. Math., 237 (2013), pp. 62-146. · Zbl 1261.05053
[12] J. Moon and L. Moser, {\it On Hamiltonian bipartite graphs}, Israel J. Math., 1 (1963), pp. 63-165. · Zbl 0119.38806
[13] A. Taylor, {\it The Regularity Method for Graphs and Digraphs}, MSci thesis, School of Mathematics, University of Birmingham, UK, 2013; also available from arXiv:1406.6531.
[14] A. Thomason, {\it Paths and cycles in tournaments}, Proc. Amer. Math. Soc., 296 (1986), pp. 167-180. · Zbl 0599.05026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.