Hamiltonian degree sequences in digraphs (Q974465)

Chvátal's theorem is a sufficient condition on the degree sequence of a graph to guarantee that the graph is Hamiltonian. The question about an analogue for digraphs was raised by \textit{C. St. J. A. Nash-Williams} [``Hamiltonian circuits,'' Stud. Graph Theory, Part II, MAA Stud. Math. 12, 301--360 (1975; Zbl 0325.05113)]. Besides the discussion of some conjectures by Nash-Williams, Thomassen and Kelly about this possible analogue, the author provides the following approximate solution to the question. For every \(\eta>0\) there exists an integer \(n_0\) such that if \(G\) is a digraph of order \(n\geq n_0\) with out-degree sequence \(d_1^+\leq\cdots\leq d_n^+\) and in-degree sequence \(d_1^-\leq\cdots\leq d_n^-\) satisfying {\parindent=7mm \begin{itemize}\item[(i)]\(d_i^+\geq i+\eta n\) or \(d_{n-i-\eta n}^- \geq n-i\), and \item[(ii)]\(d_i^-\geq i+\eta n\) or \(d_{n-i-\eta n}^+\geq n-i\), for all \(i<n/2\), \end{itemize}} then \(G\) is pancyclic (in particular Hamiltonian). Also, they prove that for regular tournaments \(G\) of order \(n\) large enough, if \(A\) is a set of less than \((n-1)/2\) edges, then \(G-A\) contains a Hamiltonian cycle. This proves that a conjecture by \textit{C. Thomassen} [``Edge-disjoint Hamiltonian paths and cycles in tournaments,'' Proc. London Math. Soc., III. Ser. 45, 151--168 (1982; Zbl 0486.05049)] is true for tournaments of order large enough.