2014/04/23 by Samvel Kh. Darbinyan, Darbinyan, Samvel Kh., Iskandar A. Karapetyan +1 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1404.5780
openalex publication_date 2014/04/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \cite[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 the complete bipartite digraph (or to the complete bipartite digraph minus one arc) with partite sets of cardinalities of n/2 and n/2. 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).