Vertex-oriented Hamilton cycles in directed graphs (Q2380274)

Summary: Let \(D\) be a directed graph of order \(n\). An anti-directed Hamilton cycle \(H\) in \(D\) is a Hamilton cycle in the graph underlying \(D\) such that no pair of consecutive arcs in \(H\) form a directed path in \(D\). We prove that if \(D\) is a directed graph with even order \(n\) and if the indegree and the outdegree of each vertex of \(D\) is at least \(\frac23n\) then \(D\) contains an anti-directed Hamilton cycle. This improves a bound of \textit{D. D. Grant} [Ars Comb. 10, 205--209 (1980; Zbl 0448.05034)]. Let \(V(D)=P\cup Q\) be a partition of \(V(D)\). A \((P,Q)\) vertex-oriented Hamilton cycle in \(D\) is a Hamilton cycle \(H\) in the graph underlying \(D\) such that for each \(v\in P\), consecutive arcs of \(H\) incident on \(v\) do not form a directed path in \(D\), and, for each \(v\in Q\), consecutive arcs of \(H\) incident on \(v\) form a directed path in \(D\). We give sufficient conditions for the existence of a \((P,Q)\) vertex-oriented Hamilton cycle in \(D\) for the cases when \(|P|\geq \frac23n\) and when \(\frac13n\leq|P|\leq \frac23n\). This sharpens a bound given by Badheka et al. in [\textit{S. K. Tipnis} and \textit{M. J. Plantholt}, Ars Comb. 83, 257--265 (2007; Zbl 1174.05103)].