Ore-type condition for antidirected Hamilton cycles in oriented graphs
Authors
Junqing Cai
Guanghui Wang
Yun Wang
Zhiwei Zhang
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 $σ_{+-}(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, $$σ_{+-}(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 $σ_{+-}(G)\geqslant n$ contains a directed Hamilton cycle. Very recently, this result was generalized to oriented graphs under the condition $σ_{+-}(G)\geqslant(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 $σ_{+-}(G)\geqslant(3n+2)/4$ contains an antidirected Hamilton cycle. Moreover, we show that this degree condition is best possible.
