2015•Unpublished venueRequires access

On Hamiltonian bypasses in digraphs with the condition of Y. Manoussakis

Samvel Kh. Darbinyan

Open publisher page 4 citations

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.

About this research paper

What this paper is about

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.

Why it matters

OpenAlex reports 4 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available 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.

Key concepts: Hamiltonian path, Hamiltonian (control theory), Combinatorics, Digraph, Bipartite graph, Directed graph, Graph, Mathematics

Related papers

Back to paper searchBrowse research topicsOriginal source
On Hamiltonian bypasses in digraphs with the condition of Y. Manoussakis — Research Paper | ScholarLens