On Hamiltonian bypasses in digraphs with the condition of Y. Manoussakis
Samvel Kh. Darbinyan
Abstract
Samvel Kh. Darbinyan
Abstract
Let D be a strongly connected directed graph of order n ≥ 4 which satisfies the following condition for every triple x, y, z of vertices such that x and y are nonadjacent: If there is no arc from x to z, then d(x)+d(y)+d+(x)+d-(z) ≥ 3n-2. If there is no arc from z to x, then d(x)+d(y)+d-(x)+d+(z) ≥ 3n-2. In [15] (J. of Graph Theory, Vol.16, No. 5, 51-59, 1992) Y. Manoussakis proved that D is Hamiltonian. In [9] it was shown that 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 with partite sets of cardinalities of n/2 and n/2. In this paper we show that D contains also a Hamiltonian bypass (i.e., a subdigraph is obtained from a Hamiltonian cycle by reversing exactly one arc) or D is isomorphic to one tournament of order five.
OpenAlex reports 4 citations for this work. Citation counts describe recorded attention and do not establish research quality.
A contribution statement is not available in the OpenAlex record.
Method details are not available in the OpenAlex metadata.
Findings are not separately available in the OpenAlex metadata.
Limitations are not available in the OpenAlex metadata.
Application details are not available in the OpenAlex metadata.
Let D be a strongly connected directed graph of order n ≥ 4 which satisfies the following condition for every triple x, y, z of vertices such that x and y are nonadjacent: If there is no arc from x to z, then d(x)+d(y)+d+(x)+d-(z) ≥ 3n-2. If there is no arc from z to x, then d(x)+d(y)+d-(x)+d+(z) ≥ 3n-2. In [15] (J. of Graph Theory, Vol.16, No. 5, 51-59, 1992) Y. Manoussakis proved that D is Hamiltonian. In [9] it was shown that 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 with partite sets of cardinalities of n/2 and n/2. In this paper we show that D contains also a Hamiltonian bypass (i.e., a subdigraph is obtained from a Hamiltonian cycle by reversing exactly one arc) or D is isomorphic to one tournament of order five.
Key concepts: Hamiltonian path, Hamiltonian (control theory), Combinatorics, Digraph, Bipartite graph, Directed graph, Graph, Mathematics