On Hamiltonian Bypasses in one Class of Hamiltonian Digraphs - Darbinyan, Samvel Kh.; Karapetyan, Iskandar A . (Mathematical Problems of Computer Science, 2021)
Let D be a strongly connected directed graph of order n ≥ 4 which satisfies the following condition (*): for every pair of non-adjacent vertices x, y with a common in-neighbour d(x) + d(y) ≥ 2n - 1 and min {d(x), d(y)} ≥ n - 1. In [2] (J. of Graph Theory 22 (2) (1996) 181-187)) J. Bang-Jensen, G. Gutin and H. Li proved that D is Hamiltonian. In [9] it was shown that if D satisfies the condition (*) and the minimum semi-degree of D at least two, then either D contains a pre-Hamiltonian cycle (i.e., 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) with equal partite sets. In this paper we show that if the minimum out-degree of D at least two and the minimum in-degree of D at least three, then D contains also a Hamiltonian bypass, (i.e., a subdigraph is obtained from a Hamiltonian cycle by reversing exactly one arc).