Ore-type condition for antidirected Hamilton cycles in oriented graphs

Abstract

An antidirected cycle in a digraph $G$ is a subdigraph whose underlying graph is a cycle, and in which no two consecutive edges form a directed path in $G$. Let $\ddot{I}{ƒ}_{+-}(G)$ be the minimum value of $d^{+}(x)+d^{-}(y)$ over all pairs of vertices $x,y$ such that there is no edge from $x$ to $y$, that is, $$\ddot{I}{ƒ}_{+-}(G)=\min \{d^{+}(x)+d^{-}(y):\{x,y\}\subseteq V(G),xy\notin E(G)\}.$$ In 1972, Woodall extended Ore's theorem to digraphs by showing that every digraph $G$ on $n$ vertices with $\ddot{I}{ƒ}_{+-}(G)⩾n$ contains a directed Hamilton cycle. Very recently, this result was generalized to oriented graphs under the condition $\ddot{I}{ƒ}_{+-}(G)⩾(3n-3)/4$. In this paper, we give the exact Ore-type degree threshold for the existence of antidirected Hamilton cycles in oriented graphs. More precisely, we prove that for sufficiently large even integer $n$, every oriented graph $G$ on $n$ vertices with $\ddot{I}{ƒ}_{+-}(G)⩾(3n+2)/4$ contains an antidirected Hamilton cycle. Moreover, we show that this degree condition is best possible.

18 pages and 2 figures