Abstract:

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 minfd(x), d(y)g > 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).
; Доказывается, что любой сильно связный n -вершинный (n > 3) ор гр аф , который удовлетворяе т одному достаточному условию гамильтоновости орграфов (J.of Graph Theory 22(2) (1996) 181-187) и имеет минимальную полустепень исхода и зах од а не меншье чем 2 и 3, соотве тственно, содежит гамильтоновый обход, т.е., контур, который получается из гамильтонового контура после переориентации одной дуги.

Date submitted:

20.12.2013

Date accepted:

28 .02 .2014

Identifier:

oai:noad.sci.am:135955

ISSN:

0131-4645

Language:

English

Journal or Publication Title:

Mathematical Problems of Computer Science

Volume:

41

URL:

Additional Information:

isko@ipia.sci.am ; samdarbin@ipia.sci.am

Affiliation:

Institute for Informatics and Automation Problems

Country:

Armenia

Indexing:

ASCI