A new sufficient condition for a digraph to be Hamiltonian (Q1302145)

The following famous theorem is due to Meyniel: Every strongly connected digraph \(D\) of order \(n\) with the property that \(d(x)+ d(y)\geq 2n-1\), for every pair \((x,y)\) of non-adjacent vertices, is Hamiltonian. \textit{J. Bang-Jensen}, \textit{G. Gutin} and \textit{H. Li} [J. Graph Theory 22, No. 2, 181-187 (1996; Zbl 0854.05067)] conjectured that it suffices to consider only pairs \((x,y)\) such that \(x\), \(y\) dominate or are dominated by a vertex in \(D\) (and \(D\) remains Hamiltonian). In this paper, it is proved that if one replaces \(2n-1\) with \({5\over 2} n-4\) then \(D\) is indeed Hamiltonian. Some other results supporting the above conjecture are also proved.