A new sufficient condition for a Digraph to be Hamiltonian-A proof of Manoussakis Conjecture

Abstract

Y. Manoussakis (J. Graph Theory 16, 1992, 51-59) proposed the following conjecture. \noindent\textbf{Conjecture}. {\it Let $D$ be a 2-strongly connected digraph of order $n$ such that for all distinct pairs of non-adjacent vertices $x$, $y$ and $w$, $z$, we have $d(x)+d(y)+d(w)+d(z)\ge 4n-3$. Then $D$ is Hamiltonian.} In this paper, we confirm this conjecture. Moreover, we prove that if a digraph $D$ satisfies the conditions of this conjecture and has a pair of non-adjacent vertices $\{x,y\}$ such that $d(x)+d(y)\le 2n-4$, then $D$ contains cycles of all lengths $3,4,\dots ,n$.

24 pages

References in corpus (2)

• Notes on a conjecture of Manoussakis concerning Hamilton cycles in digraphs
• On pre-Hamiltonian Cycles in Hamiltonian Digraphs