\(k\)-Ordered Hamilton cycles in digraphs (Q958680): Difference between revisions

Given a digraph \(D\), let \(\delta^0(D)=\min\{\delta^+(D),\delta^-(D)\}\) be the minimum semi-degree. \(D\) is \(k\)-ordered Hamiltonian if for every sequence \(s_1,\dots,s_k\) of distinct vertices of \(D\) there is a Hamiltonian cycle which encounters \(s_1,\dots,s_k\) in this order. In the paper it is proved that every digraph \(D\) of sufficiently large order \(n\) with \(\delta^0(D)\geq\lceil(n+k)/2\rceil-1\) is \(k\)-ordered Hamiltonian. The bound on the minimum semi-degree is best possible and the proof shows that it suffices to take \(n\geq ck^9\) for a constant \(c\).