On longest non-Hamiltonian Cycles in Digraphs with the Conditions of Bang-Jensen, Gutin and Li

Abstract

Let $D$ be a strong digraph on $n\ge 4$ vertices. In [2, J. Graph Theory 22 (2) (1996) 181-187)], J. Bang-Jensen, G. Gutin and H. Li proved the following theorems: If (*) $d(x)+d(y)\ge 2n-1$ and $min\{d(x),d(y)\}\ge n-1$ for every pair of non-adjacent vertices $x,y$ with a common in-neighbour or (**) $min\{d^{+}(x)+d^{-}(y),d^{-}(x)+d^{+}(y)\}\ge n$ for every pair of non-adjacent vertices $x,y$ with a common in-neighbour or a common out-neighbour, then $D$ is hamiltonian. In this paper we show that: (i) if $D$ satisfies the condition (*) and the minimum semi-degree of $D$ at least two or (ii) if $D$ is not directed cycle and satisfies the condition (**), then either $D$ contains a cycle of length $n-1$ or $n$ is even and $D$ is isomorphic to complete bipartite digraph or to complete bipartite digraph minus one arc.

12 pages