On Hamiltonian Bypasses in Digraphs satisfying Meyniel-like Condition

Abstract

Let $G$ be a strongly connected directed graph of order $p\ge 3$. In this paper, we show that if $d(x)+d(y)\ge 2p-2$ (respectively, $d(x)+d(y)\ge 2p-1$) for every pair of non-adjacent vertices $x,y$, then $G$ contains a Hamiltonian path (with only a few exceptional cases that can be clearly characterized) in which the initial vertex dominates the terminal vertex (respectively, $G$ contains two distinct verteces $x$ and $y$ such that there are two internally disjoint $(x,y)$-paths of lengths $p-2$ and $2$).

23 pages. arXiv admin note: text overlap with arXiv:1405.0002