Article_Darbinyan.DVI


Mathematical Problems of Computer Science 41, 23{37, 2014.

On H amiltonian B ypasses in one Class of H amiltonian

Digr aphs

S a m ve l K h . D a r b in ya n a n d Is ka n d a r A . K a r a p e t ya n

Institute for Informatics and Automation Problems of NAS RA

e-mail: samdarbin@ipia.sci.am, isko@ipia.sci.am

Abstract

Let D be a strongly connected directed graph of order n ¸ 4 which satis¯es 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 satis¯es 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).

Keywords: Digraphs, Cycles, Hamiltonian cycles, Hamiltonian bypasses.

1 . In t r o d u c t io n

Th e d ir e c t e d g r a p h ( d ig r a p h ) D is H a m ilt o n ia n if it c o n t a in s a H a m ilt o n ia n c yc le , i.e ., a
c yc le t h a t in c lu d e s e ve r y ve r t e x o f D. A H a m ilt o n ia n b yp a s s in D is a s u b d ig r a p h o b t a in e d
fr o m a H a m ilt o n ia n c yc le b y r e ve r s in g e xa c t ly o n e a r c . W e r e c a ll t h e fo llo win g we ll-kn o wn
d e g r e e c o n d it io n s ( Th e o r e m s 1 -5 ) t h a t g u a r a n t e e t h a t a d ig r a p h is H a m ilt o n ia n .
T heor em 1: ( N a s h -W illia m s [1 4 ]) . L et D be a digraph of order n such that for every vertex
x, d+ ( x ) ¸ n= 2 and d¡ ( x ) ¸ n=2 , then D is Hamiltonian.
T heor em 2: ( Gh o u ila -H o u r i [1 2 ]) . L et D be a strong digraph of order n. If d( x ) ¸ n for
all vertices x 2 V ( D ) , then D is Hamiltonian.
T heor em 3: ( W o o d a ll [1 6 ]) . L et D be a digraph of order n ¸ 2 . If d+ ( x ) + d¡ ( y ) ¸ n for
all pairs of vertices x and y such that there is no arc from x to y, then D is Hamiltonian.
T heor em 4: ( Me yn ie l [1 3 ]) . L et D be a strong digraph of order n ¸ 2 . If d ( x) +d( y ) ¸ 2 n¡ 1
for all pairs of non-adjacent vertices in D, then D is Hamiltonian.

It is e a s y t o s e e t h a t Me yn ie l's t h e o r e m is a c o m m o n g e n e r a liz a t io n o f Gh o u ila -H o u r i's
a n d W o o d a ll's t h e o r e m s . Fo r a s h o r t p r o o f o f Th e o r e m 1 .3 , s e e [5 ].

C. Th o m a s s e n [1 5 ] ( fo r n = 2 k+1 ) a n d S . D a r b in ya n [6 ] ( fo r n = 2 k ) p r o ve d t h e fo llo win g :
T heor em 5: [1 5 , 6 ]. If D is a digraph of order n ¸ 5 with minimum degree at least n¡ 1 and

2 3



2 4 On Hamiltonian Bypasses in one Class of Hamiltonian Digraphs

with minimum semi-degree at least n= 2 ¡ 1 , then D is Hamiltonian (unless some extremal
cases which are characterized).

In vie w o f t h e n e xt t h e o r e m s we n e e d t h e fo llo win g d e ¯ n it io n s .
De¯nition 1: L et D0 denote any digraph of order n ¸ 5 , n odd, such that V ( D0 ) = A [ B,
where A \ B = ;, A is an independent set with ( n + 1 ) =2 vertices, B is a set of ( n ¡ 1 ) =2
vertices inducing any arbitrary subdigraph, and D0 has ( n + 1 ) ( n ¡ 1 ) =2 arcs between A and
B. Note that D0 has no Hamiltonian bypass.
De¯nition 2: F or any k 2 [1 ; n ¡ 2 ] let D1 denote a digraph of order n ¸ 4 , obtained from
K¤n¡k and K

¤
k+1 by identifying a vertex of the ¯rst with a vertex of the second. Note that D1

has no Hamiltonian bypass.
De¯nition 3: B y T ( 5 ) we denote a tournament of order 5 with vertex set V ( T ( 5 ) ) =
fx1; x2; x3; x4; yg and arc set A( T ( 5 ) ) = fxixi+1=i 2 [1 ; 3 ]g [ fx4x1; x1y; x3y; yx2;
yx4; x1x3; x2x4g. T ( 5 ) has no Hamiltonian bypass.

In [4 ] it wa s p r o ve d t h a t if a d ig r a p h D s a t is ¯ e s t h e c o n d it io n o f N a s h -W illia m s ' o r
Gh o u ila -H o u r i's o r W o o d a ll's t h e o r e m , t h e n D c o n t a in s a H a m ilt o n ia n b yp a s s . In [4 ] t h e
fo llo win g t h e o r e m wa s a ls o p r o ve d :
T heor em 6: ( B e n h o c in e [4 ]) . E very strongly 2-connected digraph of order n and with mini-
mum degree at least n¡ 1 contains a Hamiltonian bypass, unless D is isomorphic to a digraph
of type D0.

In [7 ] t h e ¯ r s t a u t h o r p r o ve d t h e fo llo win g t h e o r e m :
T heor em 7: ( D a r b in ya n [7 ]) .L et D be a strong digraph of order n ¸ 3 . If d( x ) +d( y ) ¸ 2 n¡ 2
for all pairs of non-adjacent vertices in D, then D contains a Hamiltonian bypass unless it
is isomorphic to a digraph of the set D0 [ fD1; T5; C3g, where C3 is a directed cycle of length
3.

Fo r n ¸ 3 a n d k 2 [2 ; n], D ( n; k ) d e n o t e s t h e d ig r a p h o f o r d e r n o b t a in e d fr o m a d ir e c t e d
c yc le C o f le n g t h n b y r e ve r s in g e xa c t ly k ¡ 1 c o n s e c u t ive a r c s . Th e ¯ r s t a u t h o r [7 , 8 ] h a s
s t u d ie d t h e p r o b le m o f t h e e xis t e n c e o f D ( n; 3 ) in d ig r a p h s wit h t h e c o n d it io n o f Me yn ie l's
t h e o r e m a n d in o r ie n t e d g r a p h s wit h la r g e in -d e g r e e s a n d o u t -d e g r e e s .
T heor em 8: ( D a r b in ya n [7 ]) . L et D be a strong digraph of order n ¸ 4 . If d ( x) + d( y ) ¸
2 n ¡ 1 for all pairs of non-adjacent vertices in D, then D contains a D ( n; 3 ) .
T heor em 9: ( D a r b in ya n [8 ]) . L et D be an oriented graph of order n ¸ 1 0 . If the minimum
in-degree and out-degree of D at least ( n ¡ 3 ) = 2 , then D contains a D ( n; 3 ) .

E a c h o f Th e o r e m s 1 -5 im p o s e s a d e g r e e c o n d it io n o n a ll p a ir s o f n o n -a d ja c e n t ve r t ic e s ( o r
o n a ll ve r t ic e s ) . Th e fo llo win g t h e o r e m ( a s we ll a s Th e o r e m s 1 3 a n d 1 4 ) im p o s e s a d e g r e e
c o n d it io n o n ly fo r s o m e p a ir s o f n o n -a d ja c e n t ve r t ic e s .
T heor em 10: [2 ] (B ang-J ensen, Gutin, H.L i [2]). L et D be a strong digraph of order n ¸ 2 .
Suppose that

minfd ( x) ; d( y ) g ¸ n ¡ 1 and d( x ) + d( y ) ¸ 2 n ¡ 1 ( ¤ )

for every pair of non-adjacent vertices x; y with a common in-neighbour, then D is Hamil-
tonian.

In [9 ] t h e fo llo win g r e s u lt s we r e o b t a in e d :
T heor em 11: [9 ]. L et D be a strong digraph of order n ¸ 3 with the minimum semi-degree
of D at least two. Suppose that D satis¯es the condition (*). Then either D contains a
pre-Hamiltonian cycle 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 n= 2 and
n=2 .



S. Darbinyan and I. Karapetyan 2 5

In t h is p a p e r u s in g Th e o r e m 1 1 we p r o ve t h e fo llo win g :
T heor em 12: ( Ma in R e s u lt ) . L e t D b e a s t r o n g d ig r a p h o f o r d e r n ¸ 4 wit h t h e m in im u m
o u t -d e g r e e a t le a s t t wo a n d wit h m in im u m in -d e g r e e a t le a s t t h r e e . S u p p o s e t h a t

minfd( x ) ; d( y ) g ¸ n ¡ 1 a n d d ( x) + d ( y ) ¸ 2 n ¡ 1 ( ¤ )

fo r e ve r y p a ir o f n o n -a d ja c e n t ve r t ic e s x; y wit h a c o m m o n in -n e ig h b o u r . Th e n D c o n t a in s
a H a m ilt o n ia n b yp a s s .

2 . Te r m in o lo g y a n d N o t a t io n s

W e s h a ll a s s u m e t h a t t h e r e a d e r is fa m ilia r wit h t h e s t a n d a r d t e r m in o lo g y o n t h e d ir e c t e d
g r a p h s ( d ig r a p h s ) a n d r e fe r t h e r e a d e r t o [1 ] fo r t e r m in o lo g y n o t d is c u s s e d h e r e . In t h is
p a p e r we c o n s id e r ¯ n it e d ig r a p h s wit h o u t lo o p s a n d m u lt ip le a r c s . Fo r a d ig r a p h D, we
d e n o t e b y V ( D ) t h e ve r t e x s e t o f D a n d b y A ( D ) t h e s e t o f a r c s in D. Th e o r d e r o f D
is t h e n u m b e r o f it s ve r t ic e s . Oft e n we will wr it e D in s t e a d o f A ( D ) a n d V ( D ) . Th e a r c
o f a d ig r a p h D d ir e c t e d fr o m x t o y is d e n o t e d b y xy o r x ! y. If x; y; z a r e d is t in c t
ve r t ic e s in D, t h e n x ! y ! z d e n o t e s t h a t xy a n d yz 2 D. Two d is t in c t ve r t ic e s x a n d
y a r e a d ja c e n t if xy 2 A ( D ) o r yx 2 A ( D ) ( o r b o t h ) . B y a ( x; y ) we d e n o t e t h e n u m b e r
o f a r c s wit h e n d ve r t ic e s x a n d y, in p a r t ic u la r , a( x; y ) m e a n s t h a t t h e ve r t ic e s x a n d y
a r e n o n -a d ja c e n t . Fo r d is jo in t s u b s e t s A a n d B o f V ( D ) we d e ¯ n e A( A ! B ) a s t h e s e t
fxy 2 A ( D ) =x 2 A; y 2 Bg a n d A( A; B ) = A ( A ! B ) [ A( B ! A) . If x 2 V ( D ) a n d
A = fxg we wr it e x in s t e a d o f fxg. If A a n d B a r e t wo d is t in c t s u b s e t s o f V ( D ) s u c h t h a t
e ve r y ve r t e x o f A d o m in a t e s e ve r y ve r t e x o f B, t h e n we s a y t h a t A d o m in a t e s B, d e n o t e d
b y A ! B. Th e o u t -n e ig h b o r h o o d o f a ve r t e x x is t h e s e t N + ( x ) = fy 2 V ( D ) =xy 2 A( D ) g
a n d N ¡ ( x ) = fy 2 V ( D ) =yx 2 A( D ) g is t h e in -n e ig h b o r h o o d o f x. S im ila r ly, if A µ V ( D ) ,
t h e n N + ( x; A) = fy 2 A=xy 2 A ( D ) g a n d N ¡ ( x; A) = fy 2 A=yx 2 A( D ) g. Th e o u t -
d e g r e e o f x is d+ ( x ) = jN + ( x ) j a n d d¡ ( x ) = jN ¡ ( x ) j is t h e in -d e g r e e o f x. S im ila r ly,
d+ ( x; A ) = jN + ( x; A) j a n d d¡ ( x; A ) = jN¡ ( x; A ) j. Th e d e g r e e o f t h e ve r t e x x in D is d e ¯ n e d
a s d ( x) = d+ ( x ) + d¡ ( x) ( s im ila r ly, d ( x; A ) = d+ ( x; A ) + d¡ ( x; A) ) . Th e p a t h ( r e s p e c t ive ly,
t h e c yc le ) c o n s is t in g o f t h e d is t in c t ve r t ic e s x1; x2; : : : ; xm ( m ¸ 2 ) a n d t h e a r c s xixi+1,
i 2 [1 ; m ¡ 1 ] ( r e s p e c t ive ly, xixi+1, i 2 [1 ; m ¡ 1 ], a n d xmx1 ) , is d e n o t e d b y x1x2 ¢ ¢ ¢ xm
( r e s p e c t ive ly, b y x1x2 ¢ ¢ ¢ xmx1 ) . W e s a y t h a t x1x2 ¢ ¢ ¢ xm is a p a t h fr o m x1 t o xm o r is a n
( x1; xm ) -p a t h . Fo r a c yc le Ck := x1x2 ¢ ¢ ¢ xkx1 o f le n g t h k, t h e s u b s c r ip t s c o n s id e r e d m o d u lo
k, i.e ., xi = xs fo r e ve r y s a n d i s u c h t h a t i ´ s ( m o d k ) . If P is a p a t h c o n t a in in g a s u b p a t h
fr o m x t o y we le t P [x; y] d e n o t e t h a t s u b p a t h . S im ila r ly, if C is a c yc le c o n t a in in g ve r t ic e s x
a n d y, C[x; y] d e n o t e s t h e s u b p a t h o f C fr o m x t o y. Fo r a n u n d ir e c t e d g r a p h G, we d e n o t e
b y G¤ t h e s ym m e t r ic d ig r a p h o b t a in e d fr o m G b y r e p la c in g e ve r y e d g e xy wit h t h e p a ir xy,
yx o f a r c s . Kp;q d e n o t e s t h e c o m p le t e b ip a r t it e g r a p h wit h p a r t it e s e t s o f c a r d in a lit ie s p a n d
q. Fo r in t e g e r s a a n d b, a · b, le t [a; b] d e n o t e t h e s e t o f a ll in t e g e r s wh ic h a r e n o t le s s t h a n
a a n d a r e n o t g r e a t e r t h a n b. B y D ( n; 2 ) = [x1xn; x1x2 : : : xn] is d e n o t e d t h e H a m ilt o n ia n
b yp a s s o b t a in e d fr o m a H a m ilt o n ia n c yc le x1x2 : : : xnx1 b y r e ve r s in g t h e a r c xnx1.

3 . P r e lim in a r ie s

Th e fo llo win g we ll-kn o wn s im p le L e m m a s 1 a n d 2 a r e t h e b a s is o f o u r r e s u lt s a n d o t h e r
t h e o r e m s o n d ir e c t e d c yc le s a n d p a t h s in d ig r a p h s . Th e y will b e u s e d e xt e n s ive ly in t h e



2 6 On Hamiltonian Bypasses in one Class of Hamiltonian Digraphs

p r o o f o f o u r r e s u lt .
Lemma 1: [1 1 ]. L et D be a digraph of order n ¸ 3 containing a cycle Cm, m 2 [2 ; n ¡ 1 ].
L et x be a vertex not contained in this cycle. If d ( x; Cm ) ¸ m + 1 , then D contains a cycle
Ck for all k 2 [2 ; m + 1 ].

Th e fo llo win g le m m a is a s lig h t m o d i¯ c a t io n o f a le m m a b y B o n d y a n d Th o m a s s e n [5 ].
Lemma 2: L et D be a digraph of order n ¸ 3 containing a path P := x1x2 : : : xm, m 2
[2 ; n ¡ 1 ] and let x be a vertex not contained in this path. If one of the following conditions
holds:

(i) d ( x; P ) ¸ m + 2 ;
(ii) d ( x; P ) ¸ m + 1 and xx1 =2 D or xmx1 =2 D;
(iii) d ( x; P ) ¸ m, xx1 =2 D and xmx =2 D,
then there is an i 2 [1 ; m ¡ 1 ] such that xix; xxi+1 2 D (the arc xixi+1 is a partner of

x), i.e., D contains a path x1x2 : : : xixxi+1 : : : xm of length m (we say that x can be inserted
into P or the path x1x2 : : : xixxi+1 : : : xm is extended from P with x).
De¯nition 4: ( [1 ], [2 ]) . L et Q = y1y2 : : : ys be a path in a digraph D (possibly, s = 1 ) and
let P = x1x2 : : : xt, t ¸ 2 , be a path in D ¡ V ( Q) . Q has a partner on P if there is an arc
(the partner of Q) xixi+1 such that xiy1; ysxi+1 2 D. In this case the path Q can be inserted
into P to give a new ( x1; xt ) -path with vertex set V ( P ) [ V ( Q ) . The path Q has a collection
of partners on P if there are integers i1 = 1 < i2 < ¢ ¢ ¢ < im = s + 1 such that, for every
k = 2 ; 3 ; : : : ; m the subpath Q[yik¡1; yik¡1] has a partner on P .
Lemma 3: ( [1 ], [2 ], Mu lt i-In s e r t io n L e m m a ) . L et Q = y1y2 : : : ys be a path in a digraph D
(possibly, s = 1 ) and let P = x1x2 : : : xt, t ¸ 2 , be a path in D ¡ V ( Q) . If Q has a collection
of partners on P , then there is an ( x1; xt ) -path with vertex set V ( P ) [ V ( Q) .

Th e fo llo win g le m m a is o b vio u s .
Lemma 4: L et D be a digraph of order n ¸ 3 and let C := x1x2 : : : xn¡1x1 be an arbitrary
cycle of length n ¡ 1 in D and let y be the vertex not on C. If D contains no Hamiltonian
bypass, then

(i) d+ ( y; fxi; xi+1g ) · 1 and d¡ ( y; fxi; xi+1g ) · 1 for all i 2 [1 ; n ¡ 1 ];
(ii) d+ ( y ) · ( n ¡ 1 ) = 2 , d¡ ( y ) · ( n ¡ 1 ) =2 and d ( y ) · n ¡ 1 ;
(iii) if xky; yxk+1 2 D, then xi+1xi =2 D for all xi 6= xk.
L e t D b e a d ig r a p h o f o r d e r n ¸ 3 a n d le t Cn¡1 b e a c yc le o f le n g t h n ¡ 1 in D. If fo r t h e

ve r t e x y =2 Cn¡1, d( y ) ¸ n, t h e n we s a y t h a t Cn¡1 is a g o o d c yc le . N o t ic e t h a t , b y L e m m a
4 ( ii) , if a d ig r a p h D c o n t a in s a g o o d c yc le , t h e n D a ls o c o n t a in s a H a m ilt o n ia n b yp a s s .

W e n o w n e e d t o s t a t e a n d p r o ve s o m e g e n e r a l le m m a s .
Lemma 5: L et D be a digraph of order n ¸ 6 with minimum semi-degree at least two
satisfying the condition (*). L et C := x1x2 : : : xn¡1x1 be an arbitrary cycle of length n ¡ 1
in D and let y be the vertex not on C. Then for any i 2 [1 ; n ¡ 1 ] the following holds:

(i) If yxi =2 D and xi¡2xi =2 D, then xi has a partner on C[xi+1; xi¡2] or d( xi ) ¸ n ¡ 1 .
(ii) If yxi =2 D and d( xi ) · n ¡ 2 , then xi has a partner on C[xi+1; xi¡2] or there is a

vertex xk 2 C[xi+1; xi¡2] such that fxk; xk+1; : : : ; xi¡2g ! xi.
(iii) If yxi 2 D , xi¡2xi =2 D and d¡ ( xi ) ¸ 3 , then xi has a partner on C[xi+1; xi¡1] or

d( xi ) ¸ n ¡ 1 .
P r oof: ( i) Th e p r o o f is b y c o n t r a d ic t io n . A s s u m e t h a t xi h a s n o p a r t n e r o n C[xi+1; xi¡2]

a n d d ( xi ) · n ¡ 2 . S in c e d¡ ( xi; fy; xi¡2g ) = 0 a n d d¡ ( xi ) ¸ 2 , t h e r e is a n xk 2 C[xi+1; xi¡3]
s u c h t h a t xkxi 2 D. Fr o m xk ! fxk+1; xig , d ( xi ) · n ¡ 2 , xixk+1 =2 D a n d t h e c o n d it io n
( * ) it fo llo ws t h a t xk+1xi 2 D. B y a s im ila r a r g u m e n t we c o n c lu d e t h a t xi¡2xi 2 D, wh ic h
is a c o n t r a d ic t io n .



S. Darbinyan and I. Karapetyan 2 7

Fo r t h e p r o o fs o f ( ii) a n d ( iii) we c a n u s e p r e c is e ly t h e s a m e a r g u m e n t s a s in t h e p r o o f
o f ( i) .

Lemma 6: L et D be a digraph of order n ¸ 6 with minimum semi-degree at least two
satisfying the condition (*). L et C := x1x2 : : : xn¡1x1 be an arbitrary cycle of length n ¡ 1
in D and let y be the vertex not on C. Then

(i) If for some i 2 [1 ; n ¡ 1 ], xiy 2 D and xi+1; y are non-adjacent or (ii) a( xi; y ) = 2 or
(iii) d ( y ) ¸ n ¡ 1 , then D contains a Hamiltonian bypass.

P r oof: ( i) A s s u m e t h a t ( i) is n o t t r u e . W it h o u t lo s s o f g e n e r a lit y, we a s s u m e t h a t xn¡1y 2 D,
d( y; fx1; x2; : : : ; xag ) = 0 a n d xa+1; y a r e n o n -a d ja c e n t , wh e r e a ¸ 1 . Th e n x1 a n d y is a
d o m in a t e d p a ir o f n o n -a d ja c e n t ve r t ic e s wit h a c o m m o n in -n e ig h b o u r xn¡1. Th e r e fo r e , b y
c o n d it io n ( * ) , d( y ) ¸ n ¡ 1 a n d d( x1 ) ¸ n ¡ 1 . On t h e o t h e r h a n d , u s in g L e m m a 4 ( i) we
o b t a in t h a t d( y ) · n ¡ a a n d h e n c e , a = 1 a n d d ( y ) = n ¡ 1 . Th is t o g e t h e r wit h c o n d it io n
( * ) im p lie s t h a t d( x1 ) ¸ n. If yx2 2 D, t h e n xn¡1yx2x3 : : : xn¡2xn¡1 is a g o o d c yc le in D
a n d t h e r e fo r e , D c o n t a in s a H a m ilt o n ia n b yp a s s . A s s u m e t h e r e fo r e t h a t x2y 2 D. S in c e
d( x1 ) ¸ n, b y L e m m a 2 , x1 h a s a p a r t n e r o n t h e p a t h C[x2; xn¡1], i.e , t h e r e is a n ( x2; y ) -
H a m ilt o n ia n p a t h wh ic h t o g e t h e r wit h t h e a r c x2y fo r m s a H a m ilt o n ia n b yp a s s , wh ic h is a
c o n t r a d ic t io n a n d c o m p le t e s t h e p r o o f o f ( i) .

( ii) It fo llo ws im m e d ia t e ly fr o m L e m m a s 6 ( i) a n d 4 ( i) .
( iii) S u p p o s e , o n t h e c o n t r a r y, t h a t d( y ) ¸ n ¡ 1 a n d D c o n t a in s n o H a m ilt o n ia n b yp a s s

a s we ll a s n o g o o d c yc le . B y L e m m a 4 ( ii) , d( y ) = n ¡ 1 . Fr o m L e m m a 6 ( ii) it fo llo ws t h a t
a ( y; xi ) = 1 fo r a ll i 2 [1 ; n ¡ 1 ]. W it h o u t lo s s o f g e n e r a lit y, we m a y a s s u m e t h a t ( b y L e m m a
4 ( i) )

N + ( y ) = fx1; x3; : : : ; xn¡2g a n d N¡ ( y ) = fx2; x4; : : : ; xn¡1g: ( 1 )
N o t ic e t h a t

( 2 ) fo r e ve r y ve r t e x xi, xixi¡1 =2 D a n d xi h a s n o p a r t n e r o n t h e p a t h C[xi+1; xi¡1] ( fo r
o t h e r wis e , D c o n t a in s a H a m ilt o n ia n b yp a s s ) .

A s s u m e ¯ r s t t h a t x1x3 2 D. Th e n it is n o t d i± c u lt t o s h o w t h a t x2; xn¡1 a r e n o n -a d ja c e n t
a n d x2x4 =2 D. In d e e d , b y ( 1 ) if xn¡1x2 2 D, t h e n D ( n; 2 ) = [x1x2; x1x3x4yx5 : : : xn¡1x2]; if
x2x4 2 D, t h e n D ( n; 2 ) = [x2x3; x2x4x5 : : : xn¡1yx1x3]; a n d if x2xn¡1 2 D, t h e n D ( n; 2 ) =
[x2xn¡1; x2yx1x3x4 : : : xn¡1], in e a c h c a s e we h a ve a c o n t r a d ic t io n . N o w, s in c e xn¡1x2 =2 D,
yx2 =2 D a n d x2 h a s n o p a r t n e r o n C[x3; x1], L e m m a 5 ( i) im p lie s t h a t d ( x2 ) ¸ n ¡ 1 . On t h e
o t h e r h a n d , u s in g L e m m a 2 ( ii) , a( x2; xn¡1 ) = 0 , x2x4 =2 D a n d ( 2 ) , we o b t a in

n ¡ 1 · d ( x2 ) = d( x2; fy; x1; x3g ) + d ( x2; C[x4; xn¡2]) · n ¡ 2 ;

a c o n t r a d ic t io n .
A s s u m e s e c o n d t h a t x1x3 =2 D. B y t h e s ym m e t r y o f t h e ve r t ic e s xn¡2 a n d x1 ( b y ( 1 ) ) ,

we a ls o m a y a s s u m e t h a t xn¡2x1 =2 D. S in c e x1 h a s n o p a r t n e r o n C[x3; xn¡2], a g a in u s in g
L e m m a 2 ( iii) a n d ( 2 ) we o b t a in

d( x1 ) = d( x1; fxn¡1; x2; yg ) + d ( x1; C[x3; xn¡2]) · n ¡ 2 :

Th e r e fo r e , b y c o n d it io n ( * ) , we h a ve t h a t x1 is a d ja c e n t wit h x3 a n d xn¡2, i.e ., x3x1; x1xn¡2 2
D, s in c e y ! fxn¡2; x1; x3g. N o w it is e a s y t o s e e t h a t fx3; x4; : : : ; xn¡2g ! x1, wh ic h
c o n t r a d ic t s t h a t xn¡2x1 =2 D. In e a c h c a s e we o b t a in a c o n t r a d ic t io n , a n d h e n c e , t h e p r o o f
o f L e m m a 6 ( iii) is c o m p le t e d .

Th e fo llo win g s im p le o b s e r va t io n is o f im p o r t a n c e in t h e r e s t o f t h e p a p e r .
Remar k: L et D be a digraph of order n ¸ 6 with minimum semi-degree at least two satisfying



2 8 On Hamiltonian Bypasses in one Class of Hamiltonian Digraphs

the condition (*). L et C := x1x2 : : : xn¡1x1 be an arbitrary cycle of length n ¡ 1 in D and
let y be the vertex not on C. If D contains no Hamiltonian bypass, then

(i) There are two distinct vertices xk and xl such that fxk; xk+1g \ fxl; xl+1g = ;, xk !
y ! xk+1 and xl ! y ! xl+1 (by L emmas 4(i) and 5(i)).

(ii) xi+1xi =2 D for all i 2 [1 ; n ¡ 1 ].
(iii) If y ! fxi¡1; xi+1g or fxi¡1; xi+1g ! y, then xi has no partner on the path

C[xi+1; xi¡1].
(iv) If xi+1xi¡1 2 D, then d( xi ) · n ¡ 2 (by R emark (i) and L emma 6(ii)).

Lemma 7: L et D be a digraph of order n ¸ 6 with minimum semi-degree at least two
satisfying the condition (*). L et C := x1x2 : : : xn¡1x1 be an arbitrary cycle of length n¡ 1 in D
and let y be the vertex not on C. Assume that y ! fx2; xn¡1g, x1 ! y and d( y; fx3; xn¡2g ) =
0 . Then D contains a Hamiltonian bypass.
P r oof: Th e p r o o f is b y c o n t r a d ic t io n . A s s u m e t h a t D c o n t a in s n o H a m ilt o n ia n b yp a s s . Fr o m
R e m a r k ( i) a n d L e m m a s 6 ( i) , 4 ( i) it fo llo ws t h a t fo r s o m e j 2 [4 ; n ¡ 4 ], xj ! y ! xj+1.

N o w we s h o w t h a t xn¡2x1 =2 D. A s s u m e t h a t t h is is n o t t h e c a s e . Th e n xn¡2x1 2 D
a n d d( xn¡1 ) · n ¡ 2 ( b y R e m a r k ( iv) ) . Th e n , s in c e y ! fx2; xn¡1g, t h e c o n d i-
t io n ( * ) im p lie s t h a t x2 a n d xn¡1 a r e a d ja c e n t , i.e ., x2xn¡1 2 D o r xn¡1x2 2 D. If
x2xn¡1 2 D, t h e n D ( n; 2 ) = [x2xn¡1; x2x3 : : : xn¡2x1yxn¡1], a n d if xn¡1x2 2 D, t h e n
D ( n; 2 ) = [xn¡1x1; xn¡1x2x3 : : : xjyxj+1 : : : xn¡2x1]. In b o t h c a s e s we h a ve a H a m ilt o n ia n
b yp a s s , a c o n t r a d ic t io n . Th e r e fo r e xn¡2x1 =2 D.

N o w, s in c e x1 h a s n o p a r t n e r o n C[x3; xn¡2], b y L e m m a 5 ( i) , d( x1 ) ¸ n¡ 1 . On t h e o t h e r
h a n d , fr o m d( y; fx3; xn¡2g ) = 0 , d( y ) · n ¡ 2 a n d t h e c o n d it io n ( * ) it fo llo ws t h a t x1x3 =2 D
a n d x1xn¡2 =2 D ( in p a r t ic u la r , a( x1; xn¡2 ) = 0 ) . N o w u s in g L e m m a 2 ( ii) a n d R e m a r k ( ii)
we o b t a in

n ¡ 1 · d( x1 ) = d( x1; fy; x2; xn¡1g ) + d( x1; C[x3; xn¡3]) · n ¡ 2 ;
wh ic h is a c o n t r a d ic t io n . L e m m a 7 is p r o ve d .
Lemma 8: L et D be a digraph of order n ¸ 6 with minimum semi-degree at least two
satisfying the condition (*). L et C := x1x2 : : : xn¡1x1 be an arbitrary cycle of length n ¡ 1
in D and let y be the vertex not on C. If d¡ ( y ) ¸ 3 and y is adjacent with four consecutive
vertices of the cycle C, then D contains a Hamiltonian bypass.
P r oof: S u p p o s e , o n t h e c o n t r a r y, t h a t D c o n t a in s n o H a m ilt o n ia n b yp a s s a n d n o g o o d c yc le .
U s in g L e m m a s 6 ( i) a n d 4 ( i) , wit h o u t lo s s o f g e n e r a lit y, we c a n a s s u m e t h a t fxn¡1; x2g ! y
a n d y ! fx1; x3g. B y R e m a r ks ( ii) a n d ( iii) we h a ve

( 3 ) xixi¡1 =2 D fo r e a c h i 2 [1 ; n ¡ 1 ] a n d x1 ( r e s p e c t ive ly, x2 ) h a s n o p a r t n e r o n t h e p a t h
C[x2; xn¡1] ( r e s p e c t ive ly, C[x3; x1]) .

If xn¡2x1 =2 D a n d x1x3 =2 D, t h e n u s in g L e m m a 2 ( iii) a n d ( 3 ) we o b t a in t h a t
d ( x1 ) = d( x1; fy; x2; xn¡1g ) + d( x1; C[x3; xn¡2]) · n ¡ 2 :

Th e r e fo r e , b y c o n d it io n ( * ) , t h e ve r t ic e s x1; x3 a r e a d ja c e n t , s in c e y ! fx1; x3g ( x1 a n d x3
h a s a c o m m o n in -n e ig h b o u r y ) . Th is m e a n s t h a t x3x1 2 D. S in c e x1 h a s n o p a r t n e r o n
C[x3; xn¡2], it fo llo ws fr o m x3 ! fx1; x4g a n d d( x1 ) · n ¡ 2 t h a t x4x1 2 D. S im ila r ly,
we c o n c lu d e t h a t xn¡2x1 2 D wh ic h c o n t r a d ic t s t h e a s s u m p t io n t h a t xn¡2x1 =2 D. A s s u m e
t h e r e fo r e t h a t

xn¡2x1 2 D o r x1x3 2 D: ( 4 )
N o w we p r o ve t h a t d ( x1 ) ¸ n ¡ 1 . A s s u m e t h a t t h is is n o t t h e c a s e , t h a t is

d( x1 ) · n ¡ 2 . Th e n a g a in b y c o n d it io n ( * ) x1; x3 a r e a d ja c e n t b e c a u s e o f y ! fx1; x3g.



S. Darbinyan and I. Karapetyan 2 9

Th e r e fo r e x3x1 2 D o r x1x3 2 D. If x3x1 2 D, t h e n it is n o t d i± c u lt t o s h o w t h a t
fx3; x4; : : : ; xn¡2g ! x1, i.e ., d( x1 ) ¸ n¡ 1 , a c o n t r a d ic t io n . A s s u m e t h e r e fo r e t h a t x3x1 =2 D
a n d x1x3 2 D. Th e n C0 := x1x3x4 : : : xn¡1yx1 is a c yc le o f le n g t h n ¡ 1 m is s in g t h e ve r -
t e x x2. Th e n d( x2 ) · n ¡ 2 ( b y R e m a r k ( iv) ) . N o w, s in c e x2 h a s n o p a r t n e r o n C[x3; x1]
( b y ( 3 ) ) a n d d¡ ( x2; fxi; xi+1g ) · 1 fo r a ll i 2 [3 ; n ¡ 2 ] ( b y L e m m a 4 ( i) ) , it fo llo ws t h a t
d¡ ( x2; fy; x3; x4; : : : ; xn¡2g ) = 0 . Th e n xn¡1x2 2 D b e c a u s e o f d¡ ( x2 ) ¸ 2 . Fr o m d¡ ( y ) ¸ 3
a n d L e m m a 6 ( i) it fo llo ws t h a t t h e r e is a ve r t e x xj 2 C[x4; xn¡3] s u c h t h a t xj ! y ! xj+1.
Th e r e fo r e D ( n; 2 ) = [x1x2; x1x3x4 : : : xj yxj+1 : : : xn¡1x2] is a H a m ilt o n ia n b yp a s s , a c o n t r a -
d ic t io n . Th is c o n t r a d ic t io n p r o ve s t h a t d( x1 ) ¸ n ¡ 1 .

N o t ic e t h a t xn¡1x2 =2 D, b y R e m a r k ( iv) . Fr o m ( 4 ) it fo llo ws t h a t t h e fo llo win g t wo c a s e s
a r e p o s s ib le : x1x3 2 D ( Ca s e 1 ) o r x1x3 =2 D a n d xn¡2x1 2 D ( Ca s e 2 ) .
Case 1. x1x3 2 D. Th e n d( x2 ) · n ¡ 2 ( b y R e m a r k ( iv) ) . It is e a s y t o s e e t h a t x2x4 =2 D
a n d xn¡1x2 =2 D ( if xn¡1x2 2 D, t h e n D h a s a c yc le o f le n g t h n ¡ 1 m is s in g x1, a n d h e n c e
d( x1 ) · n ¡ 2 wh ic h c o n t r a d ic t s t h a t d( x1 ) ¸ n ¡ 1 ) . Th u s , we h a ve a c o n t r a d ic t io n a g a in s t
L e m m a 5 ( i) , s in c e d ( x2 ) · n ¡ 2 , xn¡1x2 =2 D a n d x2 h a s n o p a r t n e r o n C[x3; xn¡1] ( b y ( 3 ) ) .
Case 2. x1x3 =2 D a n d xn¡2x1 2 D. It is e a s y t o s e e t h a t xn¡1x2 =2 D a n d xn¡3xn¡1 =2 D. If
yxn¡2 2 D, t h e n xn¡1 h a s n o p a r t n e r o n C[x1; xn¡2]. Th is t o g e t h e r wit h d( xn¡1 ) · n¡ 2 , a n d
xn¡3xn¡1 =2 D c o n t r a d ic t s L e m m a 5 ( i) . A s s u m e t h e r e fo r e t h a t y a n d xn¡2 a r e n o n -a d ja c e n t .
Th e n , s in c e d ( y ) · n ¡ 2 a n d x2y 2 D, we h a ve t h a t x2xn¡2 =2 D.

A s s u m e ¯ r s t t h a t x2xn¡1 2 D. Th e n xn¡2x2 =2 D ( fo r o t h e r wis e t h e a r c xn¡2xn¡1 2
C[x3; xn¡1] is a p a r t n e r o f x2 o n C[x3; xn¡1], a c o n t r a d ic t io n a g a in s t ( 3 ) ) . Th e r e fo r e x2 a n d
xn¡2 a r e n o n -a d ja c e n t . N o w we h a ve xix2 2 D, wh e r e i 2 [4 ; n ¡ 3 ] s in c e d¡ ( x2 ) ¸ 2 a n d
d¡ ( x2; fy; x3; xn¡2; xn¡1g ) = 0 . It is n o t d i± c u lt t o s e e t h a t d( x2 ) ¸ n ¡ 1 ( L e m m a 5 ( i) ) .
Th e n b y R e m a r k ( ii) a n d L e m m a 2 we o b t a in

n ¡ 1 · d ( x2 ) = d( x2; fy; x1; x3; xn¡1g ) + d ( x2; C[x4; xn¡3]) · n ¡ 1 ;

i.e ., d( x2 ) = n ¡ 1 a n d d ( x2; C[x4; xn¡3]) = n ¡ 5 . B y L e m m a 2 , x2x4 a n d xn¡3x2 2 D.
Fr o m d ( x2 ) = n ¡ 1 a n d t h e c o n d it io n ( * ) it fo llo ws t h a t d ( xn¡2 ) ¸ n, s in c e x2 a n d xn¡2
a r e n o n -a d ja c e n t a n d h a ve a c o m m o n in -n e ig h b o u r xn¡3. If x1xn¡2 2 D, t h e n D ( n; 2 ) =
[x1x2; x1xn¡2xn¡1yx3x4 : : : xn¡3x2], a c o n t r a d ic t io n . A s s u m e t h e r e fo r e t h a t x1xn¡2 =2 D.
N o w we c o n s id e r t h e c yc le C0 := xn¡3x2xn¡1yx3x4 : : : xn¡3 o f le n g t h n ¡ 2 wh ic h d o e s n o t
c o n t a in t h e ve r t ic e s xn¡2 a n d x1. S in c e d( xn¡2 ) ¸ n a n d x1xn¡2 =2 D ( i.e ., a ( x1; xn¡2 ) = 1 ) ,
t h e n d ( xn¡2; C

0 ) ¸ n ¡ 1 . Th e r e fo r e , b y L e m m a 1 , t h e r e is a c yc le , s a y C00, o f le n g t h
n ¡ 1 m is s in g t h e ve r t e x x1. Th e n , s in c e d( x1; C00 ) ¸ n ¡ 1 , b y L e m m a 4 ( ii) D c o n t a in s a
H a m ilt o n ia n b yp a s s .

A s s u m e s e c o n d t h a t x2 a n d xn¡1 a r e n o n -a d ja c e n t . Th e n , s in c e d ( xn¡1 ) · n ¡ 2 , t h e
c o n d it io n ( * ) im p lie s t h a t xn¡2x2 =2 D. Th e n b y R e m a r k ( ii) a n d L e m m a 2 ( ii) , we h a ve

d( x2 ) = d ( x2; fy; x1; x3g ) + d( x2; C[x4; xn¡2]) · n ¡ 2 :

Th is c o n t r a d ic t s L e m m a 5 ( i) ( b e c a u s e o f ( 3 ) ) a n d c o m p le t e s t h e p r o o f o f L e m m a 8 .
Fr o m L e m m a s 6 , 7 a n d 8 im m e d ia t e ly t h e fo llo win g le m m a fo llo ws :

Lemma 9: L et D be a digraph of order n ¸ 6 with minimum out-degree at least two and
with minimum in-degree at least three satisfying the condition (*). L et C := x1x2 : : : xn¡1x1
be an arbitrary cycle of length n ¡ 1 in D and let y be the vertex not on C. If the vertex
y is adjacent with three consecutive vertices of the cycle C, then D contains a Hamiltonian
bypass.



3 0 On Hamiltonian Bypasses in one Class of Hamiltonian Digraphs

Lemma 10: L et D be a digraph of order n ¸ 6 with minimum out-degree at least two and
with minimum in-degree at least three satisfying the condition (*). L et C := x1x2 : : : xn¡1x1
be an arbitrary cycle of length n ¡ 1 in D and let y be the vertex not on C. If D contains no
Hamiltonian bypass and xi¡1xi+1 2 D for some i 2 [1 ; n ¡ 1 ], then d( xi; fxi¡2; xi+2g) = 0 .
P r oof: Th e p r o o f is b y c o n t r a d ic t io n . W it h o u t lo s s o f g e n e r a lit y, we m a y a s s u m e t h a t D h a s
n o H a m ilt o n ia n b yp a s s , xn¡1x2 2 D a n d a ( x1; x3 ) ¸ 1 o r a ( x1; xn¡2 ) ¸ 1 . If a( x1; x3 ) ¸ 1
( r e s p e c t ive ly, a ( x1; xn¡2 ) ¸ 1 ) , t h e n , s in c e y is n o t a d ja c e n t wit h t h r e e c o n s e c u t ive ve r t ic e s
o f C, b y R e m a r k ( i) t h e r e e xis t s a ve r t e x xk 2 C[x3; xn¡2] ( r e s p e c t ive ly, xk 2 C[x2; xn¡3])
s u c h t h a t xk ! y ! xk+1. It is n o t d i± c u lt t o s e e t h a t C0 := C[x2; xk]yC[xk+1; xn¡1]x2 is a
c yc le o f le n g t h n¡ 1 m is s in g t h e ve r t e x x1, a n d x1 is a d ja c e n t wit h t h r e e c o n s e c u t ive ve r t ic e s
o f C0, n a m e ly wit h xn¡1; x2; x3 ( r e s p e c t ive ly, xn¡2; xn¡1; x2 ) , wh ic h is a c o n t r a d ic t io n a g a in s t
L e m m a 9 . L e m m a 1 0 is p r o ve d .
Lemma 11: L et D be a digraph of order n ¸ 6 with minimum out-degree at least two and
with minimum in-degree at least three satisfying the condition (*). L et C := x1x2 : : : xn¡1x1
be an arbitrary cycle of length n ¡ 1 in D and let y be the vertex not on C. D contains no
Hamiltonian bypass, then xi+1xi¡1 =2 D for all i 2 [1 ; n ¡ 1 ].
P r oof: Th e p r o o f is b y c o n t r a d ic t io n . W it h o u t lo s s o f g e n e r a lit y, we m a y a s s u m e t h a t
x3x1 2 D.

A s s u m e ¯ r s t t h a t t h e ve r t e x x2 h a s a p a r t n e r o n C[x4; xn¡1], i.e ., t h e r e is a n xj 2
C[x4; xn¡2] s u c h t h a t xj ! x2 ! xj+1. Fr o m d¡ ( y ) ¸ 3 a n d L e m m a 6 ( i) it fo llo ws t h a t
t h e r e e xis t s a ve r t e x xk 2 C[x3; xn¡2] d is t in c t fr o m xj s u c h t h a t xk ! y ! xk+1. Th e r e fo r e ,
if k ¸ j + 1 , t h e n D ( n; 2 ) = [x3x1; x3x4 : : : xjx2xj+1 : : : xkyxk+1 : : : xn¡1x1], a n d if k · j ¡ 1 ,
t h e n D ( n; 2 ) = [x3x1; x3x4 : : : xkyxk+1 : : : xjx2xj+1 : : : xn¡1x1], a c o n t r a d ic t io n .

A s s u m e s e c o n d t h a t x2 h a s n o p a r t n e r o n C[x4; xn¡1]. S in c e x3x1 2 D, L e m m a 1 0 im p lie s
t h a t x2x4 =2 D a n d xn¡1x2 =2 D. N o w u s in g L e m m a 2 ( iii) a n d R e m a r k ( ii) we o b t a in

d( x2 ) = d( x2; fy; x1; x3g ) + d( x2; C[x4; xn¡1]) · n ¡ 2 :

Th is t o g e t h e r wit h t h e c o n d it io n ( * ) im p lie s t h a t d¡ ( x2; C[x3; xn¡1]) = 0 . Th e r e fo r e d
¡ ( x2 ) ·

2 , wh ic h c o n t r a d ic t s t h a t d¡ ( x2 ) ¸ 3 . L e m m a 1 1 is p r o ve d .

4 . Th e P r o o f o f t h e Ma in R e s u lt

P roof of Theorem 12. B y Th e o r e m 1 1 t h e d ig r a p h D c o n t a in s a c yc le o f le n g t h n ¡ 1 o r n
is e ve n a n d D is is o m o r p h ic t o t h e c o m p le t e b ip a r t it e d ig r a p h ( o r t o t h e c o m p le t e b ip a r t it e
d ig r a p h m in u s o n a r c ) wit h e qu a l p a r t it e s e t s . If n · 5 o r D c o n t a in s n o c yc le o f le n g t h n¡ 1 ,
t h e n it is n o t d i± c u lt t o c h e c k t h a t D c o n t a in s a H a m ilt o n ia n b yp a s s . A s s u m e t h e r e fo r e
t h a t n ¸ 6 , D c o n t a in s a c yc le o f le n g t h n ¡ 1 a n d h a s n o H a m ilt o n ia n b yp a s s . Fr o m
L e m m a 9 it fo llo ws t h a t if C is a n a r b it r a r y c yc le o f le n g t h n ¡ 1 in D a n d t h e ve r t e x y
is n o t o n C, t h e n t h e r e a r e n o t t h r e e c o n s e c u t ive ve r t ic e s o f C wh ic h a r e a d ja c e n t wit h y.
L e t C := x1x2 : : : xn¡1x1 b e a n a r b it r a r y c yc le o f le n g t h n ¡ 1 in D a n d le t y b e t h e ve r t e x
n o t o n C. Th e n , b y L e m m a 6 ( i) , t h e fo llo win g t wo c a s e s a r e p o s s ib le : Th e r e is a ve r t e x
xi a n d a n in t e g e r a ¸ 1 s u c h t h a t d( y; fxi+1; xi+2; : : : ; xi+ag ) = 0 , xi¡1 ! y ! xi a n d t h e
ve r t ic e s y, xi+a+1 a r e a d ja c e n t ( Ca s e I) o r d( y; fxi+1; xi+2; : : : ; xi+ag) = 0 , y ! fxi; xi+a+2g,
xi+a+1y 2 D a n d t h e ve r t ic e s y, xi¡1 a r e n o n -a d ja c e n t , wh e r e a 2 [1 ; n ¡ 6 ].

Th e p r o o f will b e b y in d u c t io n o n a. W e will ¯ r s t s h o w t h a t t h e t h e o r e m is t r u e fo r
a = 1 .



S. Darbinyan and I. Karapetyan 3 1

Case I . a = 1 . W it h o u t lo s s o f g e n e r a lit y, we m a y a s s u m e t h a t xn¡2 ! y ! xn¡1, x2; y a r e
a d ja c e n t a n d y , x1 a r e n o n -a d ja c e n t . S in c e t h e ve r t e x y is n o t a d ja c e n t wit h t h r e e c o n s e c u t ive
ve r t ic e s o f C ( L e m m a 9 ) , it fo llo ws t h a t y; xn¡3 a ls o a r e n o n -a d ja c e n t . Co n d it io n ( * ) im p lie s
t h a t xn¡2x1 =2 D, s in c e d ( y ) · n ¡ 2 a n d xn¡2y 2 D.

W e s h o w t h a t x1 h a s a p a r t n e r o n C[x3; xn¡2]. A s s u m e t h a t t h is is n o t t h e c a s e . Th e n
b y L e m m a 5 ( i) we h a ve d( x1 ) ¸ n ¡ 1 , s in c e xn¡2x1 =2 D a n d yx1 =2 D. On t h e o t h e r h a n d ,
u s in g L e m m a 2 ( ii) a n d R e m a r k ( ii) , we o b t a in

n ¡ 1 · d( x1 ) = d( x1; fx2; xn¡1g ) + d( x1; C[x3; xn¡2]) · n ¡ 2 ;

wh ic h is a c o n t r a d ic t io n .
S o , in d e e d x1 h a s a p a r t n e r o n C[x3; xn¡2]. L e t t h e a r c xkxk+1 2 C[x3; xn¡2] b e a p a r t n e r

o f x1, i.e ., xk ! x1 ! xk+1. N o t ic e t h a t k 2 [4 ; n ¡ 4 ] ( b y L e m m a 1 1 ) . If yx2 2 D, t h e n
D ( n; 2 ) = [yxn¡1; yx2x3 : : : xkx1xk+1 : : : xn¡2xn¡1], a c o n t r a d ic t io n . A s s u m e t h e r e fo r e t h a t
yx2 =2 D. Th e n x2y, yx3 2 D a n d y, x4 a r e n o n -a d ja c e n t , b y L e m m a s 9 a n d 6 ( i) . Th is
t o g e t h e r wit h t h e c o n d it io n ( * ) im p lie s t h a t x2x4 =2 D, s in c e x2y 2 D a n d d( y ) · n ¡ 2 . If
xn¡2x2 2 D, t h e n C0 := xn¡2x2yx3 : : : xkx1xk+1 : : : xn¡2 is a c yc le o f le n g t h n ¡ 1 m is s in g t h e
ve r t e x xn¡1 fo r wh ic h fxn¡2; yg ! xn¡1. Th e n xn¡1x2 2 D, b y L e m m a s 6 ( i) a n d 4 , i.e ., xn¡1
is a d ja c e n t wit h t h r e e c o n s e c u t ive ve r t ic e s o f C0, wh ic h is c o n t r a r y t o L e m m a 9 . A s s u m e
t h e r e fo r e t h a t xn¡2x2 =2 D. N o w we s h o w t h a t x2 a ls o h a s a p a r t n e r o n C[x3; xn¡2]. A s s u m e
t h a t t h is is n o t t h e c a s e . Th e n , s in c e x2xn¡1 =2 D ( b y L e m m a 1 1 ) a n d x2x4 =2 D, u s in g
L e m m a 2 ( iii) a n d R e m a r k ( ii) we o b t a in

d( x2 ) = d ( x2; fy; x1; x3; xn¡1g ) + d( x2; C[x4; xn¡2]) · n ¡ 2 :

Th is t o g e t h e r wit h x1 ! fx2; xk+1g a n d t h e c o n d it io n ( * ) im p lie s t h a t x2, xk+1 a r e a d ja c e n t .
It is e a s y t o s e e t h a t xk+1x2 2 D. B y a s im ila r a r g u m e n t , we c o n c lu d e t h a t xn¡2x2 2 D,
wh ic h c o n t r a d ic t s t h e fa c t t h a t xn¡2x2 =2 D. Th u s , x2 a ls o h a s a p a r t n e r o n C[x3; xn¡2].
Th e r e fo r e , b y Mu lt i-In s e r t io n L e m m a t h e r e is a ( x3; xn¡1 ) -p a t h wit h ve r t e x s e t V ( C ) , wh ic h
t o g e t h e r wit h t h e a r c s yxn¡1 a n d yx3 fo r m s a H a m ilt o n ia n b yp a s s . Th is c o m p le t e s t h e
d is c u s s io n o f in d u c t io n ¯ r s t s t e p fo r ( a = 1 ) Ca s e I.

N o w we c o n s id e r t h e in d u c t io n ¯ r s t s t e p fo r Ca s e II.
Case I I . a = 1 . W it h o u t lo s s o f g e n e r a lit y, we m a y a s s u m e t h a t y ! fx3; xn¡1g, x2y 2 D
a n d d( y; fx1; x4; xn¡2g ) = 0 . B y in d u c t io n ¯ r s t s t e p o f Ca s e I, we m a y a s s u m e t h a t y; x5 a ls o
a r e n o n -a d ja c e n t . Th is t o g e t h e r wit h d ( y ) · n ¡ 2 , x2y 2 D a n d t h e c o n d it io n ( * ) im p lie s
t h a t

d+ ( x2; fx4; x5; xn¡2g ) = 0 ; ( 5 )
a n d h e n c e , b y L e m m a 1 1 , in p a r t ic u la r , t h e ve r t ic e s x2; x4 a r e n o n -a d ja c e n t . If xn¡2x1 2 D,
t h e n t h e c yc le C0 := xn¡2x1x2yx3 : : : xn¡2 h a s le n g t h n ¡ 1 m is s in g t h e ve r t e x xn¡1 a n d
fxn¡2; yg ! xn¡1 ! x1, i.e ., fo r t h e c yc le C0 a n d ve r t e x xn¡1 t h e c o n s id e r e d in d u c t io n ¯ r s t
s t e p o f Ca s e I h o ld s . A s s u m e t h e r e fo r e t h a t xn¡2x1 =2 D. Th e n x1; xn¡2 a r e n o n -a d ja c e n t
( L e m m a 1 1 ) . It is n o t d i± c u lt t o s e e t h a t x1 h a s a p a r t n e r o n C[x3; xn¡3]. In d e e d , fo r
o t h e r wis e fr o m L e m m a 5 ( i) it fo llo ws t h a t d( xn¡1 ) ¸ n ¡ 1 a n d h e n c e b y L e m m a 2 a n d
R e m a r k ( ii) , we h a ve

n ¡ 1 · d( x1 ) = d( x1; fx2; xn¡1g ) + d( x1; C[x3; xn¡3]) · n ¡ 2 ;

wh ic h is a c o n t r a d ic t io n . Th u s , in d e e d x1 h a s a p a r t n e r o n C[x3; xn¡3]. L e t t h e a r c xkxk+1 2
C[x3; xn¡3] b e a p a r t n e r o f x1. N o t e t h a t k 2 [4 ; n ¡ 4 ] ( b y L e m m a 1 1 ) . Th e r e fo r e , n e it h e r



3 2 On Hamiltonian Bypasses in one Class of Hamiltonian Digraphs

t h e ve r t e x x2 n o r t h e a r c x1x2 h a s a p a r t n e r o n C[x3; xn¡1] ( fo r o t h e r wis e , b y Mu lt i-In s e r t io n
L e m m a t h e r e is a n ( x3; xn¡1 ) -p a t h wit h ve r t e x s e t V ( C ) , wh ic h t o g e t h e r wit h t h e a r c s yx3
a n d yxn¡1 fo r m s a H a m ilt o n ia n b yp a s s ) . R e c a ll t h a t a( x2; x4 ) = 0 a n d x2x5 =2 D ( b y ( 5 ) .
N o w u s in g L e m m a 2 ( ii) a n d R e m a r k ( ii) we o b t a in t h a t

d( x2 ) = d( x2; fy; x1; x3g ) + d( x2; C[x5; xn¡1]) · n ¡ 2 :
Th is t o g e t h e r wit h x1 ! fx2; xk+1g a n d t h e c o n d it io n ( * ) im p lie s t h a t x2 a n d xk+1
a r e a d ja c e n t . Th e n xk+1x2 2 D ( if x2xk+1 2 D, t h e n t h e a r c x1x2 h a s a p a r t n e r
o n C[x3; xn¡1]) . B y a s im ila r a r g u m e n t , we c o n c lu d e t h a t fxn¡2; xn¡1g ! x2. Th e n
C0 := xn¡2x2yx3x4 : : : xkx1xk+1 : : : xn¡2 is a c yc le o f le n g t h n ¡ 1 , wh ic h d o e s n o t c o n t a in t h e
ve r t e x xn¡1 a n d d ( xn¡1; fxn¡2; x2; yg ) = 3 , a c o n t r a d ic t io n a g a in s t L e m m a 9 a n d h e n c e , t h e
d is c u s s io n o f c a s e a = 1 is c o m p le t e d .

The induction hypothesis. N o w we s u p p o s e t h a t t h e t h e o r e m is t r u e if D c o n t a in s a c yc le
C := x1x2 : : : xn¡1x1 o f le n g t h n ¡ 1 m is s in g t h e ve r t e x y fo r wh ic h t h e r e is a ve r t e x xi s u c h
t h a t d ( y; fxi+2; xi+3; : : : ; xi+jg ) = 0 a n d ( i) xi ! y ! xi+1 a n d t h e ve r t ic e s y; xi+j+1 a r e
a d ja c e n t o r ( ii) y ! fxi+1; xi+j+2g a n d xi+j+1y 2 D, wh e r e 2 · j · a · n ¡ 6 .

B e fo r e d e a lin g wit h Ca s e s I a n d II, it is c o n ve n ie n t t o p r o ve t h e fo llo win g g e n e r a l c la im .
Claim. L e t C := x1x2 : : : xn¡1x1 b e a n a r b it r a r y c yc le o f le n g t h n ¡ 1 in D a n d le t y b e
t h e ve r t e x n o t o n C a n d le t d( y; fx1; x2; : : : ; xag ) = 0 , wh e r e a ¸ 2 .If ( i) xn¡2y; yxn¡1 2 D
a n d t h e ve r t ic e s y a n d xa+1 a r e n o n -a d ja c e n t o r ( ii) xa+1y; yxa+2 a n d yxn¡1 2 D, t h e n
xk¡1xk+1 =2 D fo r a ll k 2 [1 ; a].
P r oof of the Claim: S u p p o s e , o n t h e c o n t r a r y, t h a t xk¡1xk+1 2 D fo r s o m e k 2
[1 ; a], t h e n C0 := xn¡2yxn¡1x1 : : : xk¡1xk+1 : : : xn¡2 o r C

00 := xn¡1x1 : : : xk¡1xk+1 : : : xa+1
yxa+2 : : : xn¡2xn¡1 is a c yc le o f le n g t h n ¡ 1 m is s in g t h e ve r t e x xk fo r ( i) a n d ( ii) , r e -
s p e c t ive ly. Th e r e fo r e , d( xk ) · n ¡ 2 ( b y R e m a r k ( iv) ) . B y t h e in d u c t io n h yp o t h e -
s is xk is n o t a d ja c e n t wit h ve r t ic e s xk+2; xk+3; : : : ; xk+a; xk¡2; xk¡3; : : : xk¡a. In p a r t ic u la r ,
d¡ ( xk; fxk+1; xk+2; : : : ; xa+1g) = 0 a n d d¡ ( xk; C[xn¡2; xk¡2]) = 0 ( it is e a s y t o s h o w t h a t
in b o t h c a s e s xn¡2xk =2 D ) . S in c e d( xk ) · n ¡ 2 a n d xk¡2xk =2 D, b y L e m m a 5 ( i) , t h e
ve r t e x xk h a s a p a r t n e r o n C[xa+2; xn¡2], s a y t h e a r c xjxj+1 2 C[xa+2; xn¡2] is a p a r t n e r o f
xk, i.e ., xjxk; xkxj+1 2 D. Th e r e fo r e xn¡1x1 : : : xk¡1xk+1 : : : xaxa+1 : : : xjxkxj+1 : : : xn¡2xn¡1
is a c yc le o f le n g t h n ¡ 1 m is s in g t h e ve r t e x y, fo r wh ic h d ( y; C[x1; xa] ¡ fxkg ) = 0 a n d
xn¡2y; yxn¡1 2 D, xa+1; y a r e n o n -a d ja c e n t o r yxn¡1; xa+1y; yxa+2 2 D fo r ( i) a n d ( ii) , r e -
s p e c t ive ly. Th e r e fo r e , b y t h e in d u c t io n h yp o t h e s is D c o n t a in s a H a m ilt o n ia n b yp a s s , a
c o n t r a d ic t io n t o o u r a s s u m p t io n . Th e c la im is p r o ve d . Case I . W it h o u t lo s s o f g e n e r a lit y,
we m a y a s s u m e t h a t d ( y; fx2; x3; : : : ; xa+1g) = 0 , wh e r e a ¸ 2 , xn¡1y; yx1 2 D a n d t h e
ve r t ic e s y; xa+2 a r e n o n -a d ja c e n t .

N o t ic e , t h e c o n d it io n ( * ) im p lie s t h a t fo r a ll i 2 [2 ; a + 1 ], xn¡1xi =2 D, s in c e xn¡1y 2 D,
d( y ) · n ¡ 2 a n d t h e ve r t ic e s xi; y a r e n o n -a d ja c e n t .
Subcase I .1. Th e r e a r e in t e g e r s k a n d l wit h 1 · l < k · a + 2 s u c h t h a t xkxl 2 D.
W it h o u t lo s s o f g e n e r a lit y, we a s s u m e t h a t k ¡ l is a s s m a ll a s p o s s ib le . Fr o m R e m a r k ( ii)
a n d L e m m a 1 1 it fo llo ws t h a t k¡l ¸ 3 . If e ve r y ve r t e x xi 2 C[xl+1; xk¡1] h a s a p a r t n e r o n t h e
p a t h P := xkxk+1 : : : xn¡1yx1 : : : xl, t h e n b y Mu lt i-In s e r t io n L e m m a t h e r e e xis t s a n ( xk; xl ) -
H a m ilt o n ia n p a t h , wh ic h t o g e t h e r wit h t h e a r c xkxl fo r m s a H a m ilt o n ia n b yp a s s . A s s u m e
t h e r e fo r e t h a t s o m e ve r t e x xi 2 C[xl+1; xk¡1] h a s n o p a r t n e r o n P . Fr o m t h e m in im a lit y o f
k ¡ l ¸ 3 a n d Cla im 1 it fo llo ws t h a t xi¡2 2 C[xl; xk] a n d a( xi; xi¡2 ) = 0 o r xi+2 2 C[xl; xk]
a n d a( xi; xi+2 ) = 0 . Th e r e fo r e b y t h e m in im a lit y o f k ¡ l we h a ve

d( xi; C[xl; xk]) · k ¡ l ¡ 1 : ( 6 )



S. Darbinyan and I. Karapetyan 3 3

S in c e xi h a s n o p a r t n e r o n t h e p a t h C[xk+1; xn¡1], a n d if l ¸ 2 a ls o o n C[x1; xl¡1], u s in g
L e m m a 2 wit h t h e fa c t t h a t xn¡1xi =2 D we o b t a in

d( xi; C[xk+1; xn¡1] · n ¡ k ¡ 1 a n d if l ¸ 2 ; t h e n d( xi; C[x1; xl¡1]) · l:

Th e la s t t wo in e qu a lit ie s t o g e t h e r wit h ( 6 ) g ive : if l ¸ 2 , t h e n d( xi ) · n ¡ 2 , a n d if l = 1 ,
t h e n d ( xi ) · n ¡ 3 . Th u s , d( xi ) · n ¡ 2 . In a d d it io n , Cla im 1 a n d xn¡1xi =2 D im p ly t h a t
xi¡2xi =2 D. Th e r e fo r e , b y L e m m a 5 ( i) , xi h a s a p a r t n e r o n P , wh ic h is c o n t r a r y t o o u r
a s s u m p t io n .
Subcase I .2. Fo r a n y p a ir o f in t e g e r s k a n d l wit h 1 · l < k · a + 2 , xkxl =2 D. Th e n it is
e a s y t o s e e t h a t fo r e a c h xi 2 C[x2; xa+1]) ,

d( xi; C[x1; xa+2]) · a; ( 7 )

s in c e xi¡2 2 C[x1; xa+2] a n d a ( xi; xi¡2 ) = 0 o r xi+2 2 C[x1; xa+2] a n d a ( xi; xi+2 ) = 0 .
W e ¯ r s t s h o w t h a t e ve r y ve r t e x xi 2 C[x2; xa+1] h a s a p a r t n e r o n C[xa+3; xn¡1]. A s s u m e

t h a t t h is is n o t t h e c a s e , i.e ., s o m e ve r t e x xi 2 C[x2; xa+1] h a s n o p a r t n e r o n C[xa+3; xn¡1].
Th e n , s in c e xn¡1xi =2 D, b y L e m m a 2 ( ii) we h a ve t h a t d( xi; C[xa+3; xn¡1]) · n ¡ a ¡ 3 . Th is
in e qu a lit y t o g e t e r wit h ( 7 ) g ive s d ( xi ) · n ¡ 3 , a c o n t r a d ic t io n a g a in s t L e m m a 5 ( i) , s in c e
xi¡2xi =2 D.

Th u s , e a c h ve r t e x xi 2 C[x2; xa+1] h a s a p a r t n e r o n C[xa+3; xn¡1]. Th e r e fo r e , b y Mu lt i-
In s e r t io n L e m m a t h e r e is a n ( xa+3; xn¡1 ) -p a t h , s a y R, wit h ve r t e x s e t V ( C ) ¡ fx1; xa+2g. If
yxa+2 2 D, t h e n [yx1; yxa+2Rx1] is a H a m ilt o n ia n b yp a s s . A s s u m e t h e r e fo r e t h a t yxa+2 =2 D.
Th e n xa+2y 2 D. B y L e m m a 6 ( i) a n d b y t h e in d u c t io n h yp o t h e s is , we h a ve yxa+3 2 D a n d
d( y; fxa+4; xa+5g ) = 0 . Th is t o g e t h e r wit h xa+2y 2 D, d( y ) · n ¡ 2 a n d t h e c o n d it io n ( * )
im p lie s t h a t

d+ ( xa+2; ; fxa+4; xa+5g ) = 0 ; ( 8 )
in p a r t ic u la r , b y L e m m a 1 1 , a ( xa+2; aa+4 ) = 0 . S in c e yxa+3 2 D a n d e a c h ve r t e x xi 2
C[x2; xa+1] h a s a p a r t n e r o n C[xa+3; xn¡1], t o s h o w t h a t D c o n t a in s a H a m ilt o n ia n b yp a s s ,
b y Mu lt i-In s e r t io n L e m m a it s u ± c e s t o p r o ve t h a t xa+2 a ls o h a s a p a r t n e r o n C[xa+3; xn¡1].
A s s u m e t h a t xa+2 h a s n o p a r t n e r o n C[xa+3; xn¡1]. Th e n , s in c e t h e ve r t ic e s xa a n d xa+2 a r e
n o n -a d ja c e n t ( Cla im 1 a n d L e m m a 1 1 ) , fr o m L e m m a 5 ( i) it fo llo ws t h a t d( xa+2 ) ¸ n ¡ 1 .
On t h e o t h e r h a n d , u s in g ( 7 ) , ( 8 ) , d( xa+2; fxa; xa+4g ) = 0 a n d L e m m a 2 , we o b t a in

n ¡ 1 · d ( xa+2 ) = d( xa+2; C[x1; xa+1]) + d ( xa+2; fy; xa+3 ) + d( xa+2; C[xa+5; xn¡1]) · n ¡ 3 ;

a c o n t r a d ic t io n . S o , xa+2 a ls o h a s a p a r t n e r o n C[xa+3; xn¡1] a n d t h e d is c u s s io n o f Ca s e I is
c o m p le t e d .
Case I I . W it h o u t lo s s o f g e n e r a lit y, we a s s u m e t h a t d( y; fx1; x2; : : : ; xag ) = 0 , wh e r e a ¸ 2 ,
xa+1y 2 D a n d y ! fxn¡1xa+2g.

B y t h e c o n s id e r e d Ca s e I, wit h o u t lo s s o f g e n e r a lit y, we m a y a s s u m e t h a t
d( y; fxn¡2; xa+3; xa+4g ) = 0 . S in c e xa+1y 2 D, d( y ) · n ¡ 2 a n d d( y; fx1; x2; : : : ; xa; xa+3;
xa+4; xn¡2g ) = 0 , t h e c o n d it io n ( * ) im p lie s t h a t

d+ ( xa+1; fx1; x2; : : : ; xa; xa+3; xa+4; xn¡2g ) = 0 : ( 9 )
Subcase I I .1. Th e r e a r e in t e g e r s k a n d l wit h 1 · l < k · a + 1 s u c h t h a t xkxl 2 D.

B y ( 9 ) , k 6= a + 1 . W it h o u t lo s s o f g e n e r a lit y, we a s s u m e t h a t k ¡ l is a s s m a ll a s p o s s ib le .
B y R e m a r k ( ii) a n d L e m m a 1 1 we h a ve k ¡ l ¸ 3 .



3 4 On Hamiltonian Bypasses in one Class of Hamiltonian Digraphs

W e ¯ r s t s h o w t h a t e a c h ve r t e x o f C[xl+1; xk¡1] h a s a p a r t n e r o n t h e p a t h P :=
xkxk+1 : : : xa+1y xa+2 : : : xn¡1x1 : : : xl. A s s u m e t h a t t h is is n o t t h e c a s e a n d le t xi 2
C[xl+1; xk¡1] h a ve n o p a r t n e r o n P . Th e n , s in c e xi¡2xi =2 D ( Cla im 1 ) , fr o m L e m m a 5 ( i)
a n d t h e m in im a lit y o f k ¡ l it fo llo ws t h a t d ( xi ) ¸ n ¡ 1 . On t h e o t h e r h a n d , u s in g t h e
m in im a lit y o f k ¡ l a n d t h e fa c t t h a t xi¡2 2 C[xl; xk]) a n d a( xi; xi¡2 ) = 0 o r xi+2 2 C[xl; xk]
a n d a( xi; xi+2 ) = 0 we o b t a in

d( xi; C[xl; xk]) · k ¡ l ¡ 1 :

In a d d it io n , b y L e m m a 2 a n d xa+1xi =2 D we a ls o h a ve

d( xi; C[xk+1; xa+1]) · a ¡ k + 1 a n d d( xi; C[xa+2; xl¡1]) · n ¡ a + l ¡ 2 :

S u m m in g t h e la s t t h r e e in e qu a lit ie s g ive s d( xi ) · n¡ 2 , wh ic h c o n t r a d ic t s t h a t d( xi ) ¸ n¡ 1 .
Th u s , in d e e d e a c h ve r t e x xi 2 C[xl+1; xk¡1] h a s a p a r t n e r o n P . Th e n b y Mu lt i-In s e r t io n
L e m m a t h e r e is a n ( xk; xl ) -H a m ilt o n ia n p a t h , wh ic h t o g e t h e r wit h t h e a r c xkxl fo r m s a
H a m ilt o n ia n b yp a s s .
Subcase I I .2. Th e r e a r e n o i a n d j s u c h t h a t 1 · i < j · a + 1 a n d xjxi =2 D. If e ve r y
ve r t e x xi 2 C[x1; xa+1]) h a s a p a r t n e r o n C[xa+2; xn¡1], t h e n b y Mu lt i-In s e r t io n L e m m a t h e r e
is a n ( xa+2; xn¡1 ) -p a t h , s a y R, wit h ve r t e x s e t V ( C ) . Th e r e fo r e [yxn¡1; yR] is a H a m ilt o n ia n
b yp a s s . A s s u m e t h e r e fo r e t h a t t h e r e is a ve r t e x xi 2 C[x1; xa+1] wh ic h h a s n o p a r t n e r o n
C[xa+2; xn¡1].

L e t xi¡2xi =2 D, t h e n fr o m L e m m a 5 ( i) it fo llo ws t h a t d( xi ) ¸ n ¡ 1 .
A s s u m e ¯ r s t t h a t d( xi; C[x1; xa+1]) = a ¡ 1 . U s in g L e m m a 2 we o b t a in t h a t if xi 6= xa+1,

t h e n
n ¡ 1 · d ( xi ) = d( xi; C[x1; xa+1]) + d ( xi; C[xa+2; xn¡1]) · n ¡ 2 ;

a n d , s in c e xa+1xa+3 =2 D, if xi = xa+1, t h e n

n ¡ 1 · d ( xa+1 ) = d( xa+1; C[x1; xa+1]) + d( xa+1; fy; xa+2 ) + d( xa+1; C[xa+3; xn¡1]) · n ¡ 2 ;

a c o n t r a d ic t io n .
A s s u m e s e c o n d t h a t d( xi; C[x1; xa+1]) = a. Th e n fr o m Cla im 1 a n d L e m m a 1 1 it fo llo ws

t h a t a = 2 , xi = x2, d( x2; fx1; x3g ) = 2 a n d d( x2; fxn¡1g ) = 0 . Th e n

n ¡ 1 · d( x2 ) = d ( x2; fx1; x3g ) + d ( x2; C[x4; xn¡2]) · n ¡ 2 ;
a c o n t r a d ic t io n .

L e t n o w xi¡2xi 2 D. Th e n , b y Cla im 1 , xi = x1 a n d xn¡2x1 2 D. W e c o n s id e r t h e c yc le
C0 := xn¡3xn¡2x1x2 : : : xaxa+1yxa+2 : : : xn¡3 o f le n g t h n ¡ 1 m is s in g t h e ve r t e x xn¡1. Th e n
fxn¡2; yg ! xn¡1 a n d xn¡1x1 2 D, i.e ., fo r t h e c yc le C0 a n d t h e ve r t e x xn¡1 Ca s e I h o ld s ,
s in c e jfx2; x3; : : : ; xa+1gj = a. Th e d is c u s s io n o f Ca s e II is c o m p le t e d a n d wit h it t h e p r o o f
o f t h e t h e o r e m is a ls o c o m p le t e d .

5 . Co n c lu d in g R e m a r ks

Th e fo llo win g t wo e xa m p le s o f d ig r a p h s s h o w t h a t if t h e m in im a l s e m i-d e g r e e o f a d ig r a p h
is e qu a l t o o n e , t h e n t h e t h e o r e m is n o t t r u e :

( i) L e t D ( 7 ) b e a d ig r a p h wit h ve r t e x s e t fx1; x2; : : : ; x6; yg a n d le t x1x2 : : : x6x1 b e a c yc le
o f le n g t h 6 in D ( 7 ) . Mo r e o ve r , N + ( y ) = fx1; x3; x5g, N¡ ( y ) = fx2; x4; x6g, x1x3; x3x5; x5x1 2



S. Darbinyan and I. Karapetyan 3 5

D ( 7 ) a n d D ( 7 ) h a s n o o t h e r a r c s . N o t e t h a t d¡ ( x2 ) = d
¡ ( x4 ) = d

¡ ( x6 ) = 1 a n d D ( 7 ) c o n t a in s
n o d o m in a t e d p a ir o f n o n -a d ja c e n t ve r t ic e s . It is n o t d i± c u lt t o c h e c k t h a t D ( 7 ) c o n t a in s
n o H a m ilt o n ia n b yp a s s .

( ii) L e t D ( n) b e a d ig r a p h wit h ve r t e x s e t fx1; x2; : : : ; xng a n d le t x1x2 : : : xnx1 b e a
H a m ilt o n ia n c yc le in D ( n) . Mo r e o ve r , D ( n) a ls o c o n t a in s t h e a r c s x1x3; x3x5; : : : ; xn¡2xn
( o r x1x3; x3x5; : : : ; xn¡3xn¡1; xn¡1x1 a n d D ( n) h a s n o o t h e r a r c s . N o t e t h a t D ( n) c o n t a in s
n o d o m in a t e d p a ir o f n o n -a d ja c e n t ve r t ic e s , d¡ ( x2 ) = d

+ ( x2 ) = 1 . It is n o t d i± c u lt t o c h e c k
t h a t D ( n) c o n t a in s n o H a m ilt o n ia n b yp a s s .

W e b e lie ve t h a t Th e o r e m 1 2 a ls o is t r u e if we r e qu ir e t h a t t h e m in im u m in -d e g r e e a t
le a s t t wo , in s t e a d o f t h r e e .

In [2 ] a n d [3 ] Th e o r e m 1 3 a n d Th e o r e m 1 4 we r e p r o ve d , r e s p e c t ive ly.
T heor em 13:(B ang-J ensen, Gutin, H. L i [2]). L et D be a strong digraph of order n ¸ 3 .
Suppose that minfd+ ( x ) + d¡ ( y ) ; d¡ ( x) + d+ ( y ) g ¸ n for any pair of non-adjacent vertices
x; y with a common out-neighbour or a common in-neighbour, then D is Hamiltonian.
T heor em 14:(B ang-J ensen, Guo, Yeo [3]). L et D be a strong digraph of order n ¸ 3 .
Suppose that d( x ) + d ( y ) ¸ 2 n ¡ 1 and minfd+ ( x ) + d¡ ( y ) ; d¡ ( x ) + d+ ( y ) g ¸ n ¡ 1 for any
pair of non-adjacent vertices x; y with a common out-neighbour or a common in-neighbour,
then D is Hamiltonian.

N o t e t h a t Th e o r e m 1 4 g e n e r a liz e s Th e o r e m 1 3 .

In [9 ] a n d [1 0 ] t h e fo llo win g r e s u lt s we r e p r o ve d :
T heor em 15:( [9]). L et D be a strong digraph of order n ¸ 4 which is not a directed cycle.
Suppose that minfd+ ( x ) + d¡ ( y ) ; d¡ ( x) + d+ ( y ) g ¸ n for any pair of non-adjacent vertices
x; y with a common out-neighbour or a common in-neighbour. Then either D contains a
pre-Hamiltonian cycle or n is even and D = K¤n=2;n=2.
T heor em 16: ( [10]). L et D be a strong digraph of order n ¸ 4 which is not a directed cycle.
Suppose that d( x ) + d ( y ) ¸ 2 n ¡ 1 and minfd+ ( x ) + d¡ ( y ) ; d¡ ( x ) + d+ ( y ) g ¸ n ¡ 1 for any
pair of non-adjacent vertices x; y with a common out-neighbour or a common in-neighbour.
Then D contains a pre-Hamiltonian cycle or a cycle of length n ¡ 2 .

In vie w o f Th e o r e m s 1 3 -1 6 , we p o s e t h e fo llo win g p r o b le m :
P r oblem: Ch a r a c t e r iz e t h o s e d ig r a p h s wh ic h s a t is fy t h e c o n d it io n o f Th e o r e m 1 3 o r 1 4 b u t
h a ve n o H a m ilt o n ia n b yp a s s .

Refer ences

[1 ] J. B a n g -Je n s e n , G. Gu t in , D ig r a p h s : Th e o r y, A lg o r it h m s a n d A p p lic a t io n s , S p r in g e r ,
2 0 0 0 .

[2 ] J. B a n g -Je n s e n , G. Gu t in , H . L i, \ S u ± c ie n t c o n d it io n s fo r a d ig r a p h t o b e H a m ilt o n ia n " ,
J ournal of Graph Theory, vo l. 2 2 n o . 2 , p p . 1 8 1 { 1 8 7 , 1 9 9 6 .

[3 ] J. B a n g -Je n s e n , Y . Gu o , A .Y e o , \ A n e w s u ± c ie n t c o n d it io n fo r a d ig r a p h t o b e H a m il-
t o n ia n " , D iscrete Applied M athematics, vo l. 9 5 , p p . 7 7 { 8 7 , 1 9 9 9 .

[4 ] A .B e n h o c in e , \ On t h e e xis t e n c e o f a s p e c ī e d c yc le s in d ig r a p h s wit h c o n s t r a in t s o n
d e g r e e s " , J ournal of Graph Theory, vo l. 8 , p p .1 0 1 -1 0 7 , 1 9 8 4 .

[5 ] J.A . B o n d y, C. Th o m a s s e n , \ A s h o r t p r o o f o f Me yn ie l's t h e o r e m " , D iscrete M athemat-
ics, vo l. 1 9 , n o . 1 , p p . 8 5 -9 2 , 1 9 7 7 .

[6 ] S .K h . D a r b in ya n , " A s u ± c ie n t c o n d it io n fo r t h e H a m ilt o n ia n p r o p e r t y o f d ig r a p h s wit h



3 6 On Hamiltonian Bypasses in one Class of Hamiltonian Digraphs

la r g e s e m id e g r e e s " , Akademy Nauk Armyan. SSR D oklady, ( s e e a ls o a r X iv: 1 1 1 1 .1 8 4 3 v1
[m a t h .CO] 8 N o v 2 0 1 1 ) , vo l. 8 2 , n o . 1 , p p . 6 -8 , 1 9 8 6 .

[7 ] S .K h . D a r b in ya n , \ On H a m ilt o n ia n b yp a s s e s in d ig r a p h s s a t is fyin g Me yn ie l-like c o n -
d it io n s " , M athematical P roblems in Computer Science, ( s e e a ls o P r o c e e d in g s o f 5 -t h
s c ie n c e -t e c h n ic a l c o n fe r e n c e fo r ya n g r e s e a r c h e r s , p . 2 3 , Ts a g h ka d z o r , A r m e n ia , 1 9 8 6 ) ,
( in R u s s ia n ) , vo l. 2 0 , p p .7 -1 9 , 1 9 9 8 .

[8 ] S .K h . D a r b in ya n , \ On t h e s p e c i¯ e d c yc le s in o r ie n t e d g r a p h s " , Akademy Nauk Armyan.
SSR D oklady, ( in R u s s ia n ) , vo l. 8 4 , n o . 1 , p p . 5 1 { 5 5 , 1 9 8 7 .

[9 ] S .K h . D a r b in ya n , I. A . K a r a p e t ya n , \ On lo n g e s t n o n -H a m ilt o n ia n c yc le s in d ig r a p h s
wit h t h e c o n d it io n s o f B a n g -Je n s e n , Gu t in a n d L i" , P reprint available at htte: arXiv
1207.5643v2 [math.CO], 2 0 S e p 2 0 1 2 .

[1 0 ] S .K h . D a r b in ya n , I. A . K a r a p e t ya n , \ A n o t e o n lo n g n o n -H a m ilt o n ia n c yc le s in o n e c la s s
o f d ig r a p h s " , P reprint available at htte: arXiv 1209.4456v1 [math.CO], 2 0 S e p 2 0 1 2 .

[1 1 ] R . H Äa g g kvis t , C. Th o m a s s e n , \ On p a n c yc lic d ig r a p h s " , J ournal Combinatorial Theory
Ser. B , vo l. 2 0 , p p . 2 0 { 4 0 , 1 9 7 6 .

[1 2 ] A . Gh o u ila -H o u r i, \ U n e c o n d it io n s u ± s a n t e d 'e xis t e n c e d 'u n c ir c u it h a m ilt o n ie n " ,
Comptes R endus de I'Academie des Sciences P aris Ser. A-B , n o . 2 5 1 , p p . 4 9 5 { 4 9 7 ,
1 9 6 0 .

[1 3 ] M. Me yn ie l, \ U n e c o n d it io n s u ± s a n t e d 'e xis t e n c e d 'u n c ir c u it h a m ilt o n ie n d a n s u n
g r a p h e o r ie n t e " , J ournal Combinatorial Theory Ser. B , vo l. 1 4 , p p . 1 3 7 -1 4 7 , 1 9 7 3 .

[1 4 ] C.S t .J.A . N a s h -W illia m s , \ H a m ilt o n c ir c u it s in g r a p h s a n d d ig r a p h s it . Th e m a n y fa c t s
o f g r a p h t h e o r y" , Springer L ecture Notes. 1 1 0 , p p .2 3 7 -2 4 3 , 1 9 6 9 .

[1 5 ] C. Th o m a s s e n , \ L o n g c yc le s in d ig r a p h s " , P roceeding L ondon M athematical Society,
vo l. 3 , n o . 4 2 , p p . 2 3 1 { 2 5 1 , 1 9 8 1 .

[1 6 ] D . R . W o o d a ll, \ S u ± c ie n t c o n d it io n s fo r c ir c u it s in g r a p h s " , P roceeding L ondon M ath-
ematical Society, n o . 2 4 , p p . 7 3 9 { 7 5 5 , 1 9 7 2 .

Submitted 20.12.2013, accepted 28.02.2014.

ÎáÕÙÝáñáßí³Í ѳÙÇÉïáÝÛ³Ý ·ñ³ýÝ»ñÇ ÙÇ ¹³ëÇ
ѳÙÇÉïáÝÛ³Ý ßñç³ÝóáõÙÝ»ñÇ Ù³ëÇÝ

ê. ¸³ñµÇÝÛ³Ý ¨ Æ. γñ³å»ïÛ³Ý

²Ù÷á÷áõÙ

ÎáÕÙÝáñáßí³Í ·ñ³ýÇ Ñ³ÙÇÉïáÝÛ³Ý ßñç³ÝóáõÙÁ ³Û¹ ·ñ³ýÇ ÙÇ »Ýó·ñ³ý ¿,
áñÁ ëï³óíáõÙ ¿ ѳÙÇÉïáÝÛ³Ý óÇÏÉÇ Ù»Ï ³Õ»ÕÇ ÏáÕÙÝáñáßáõÙÁ ßñç»Éáõó Ñ»ïá:
Ü»ñϳ ³ß˳ï³ÝùáõÙ ³å³óáõóíáõÙ ¿, áñ »Ã» ÏáÕÙÝáñáßí³Í ·ñ³ýÁ µ³í³ñ³ñáõÙ
¿ ѳÙÇÉïáÝÛ³ÝáõÃÛ³Ý ÙÇ Ñ³ÛïÝÇ å³ÛÙ³ÝÇ (J.of Graph Theory 22(2) (1996) 181-
187), ¨ Ýñ³ ·³·³ÃÝ»ñÇ ÷áùñ³·áõÛÝ ÙïÝáÕ ¨ ¹áõñë»ÏáÕ ³ëïÇ׳ÝÝ»ñÁ ÷áùñ
ã»Ý ѳٳå³ï³ë˳ݳµ³ñ,»ñ»ùÇó ¨ »ñÏáõëÇó, ³å³ ³Û¹ ·ñ³ýÁ å³ñáõݳÏáõÙ ¿
ѳÙÇÉïáÝÛ³Ý ßñç³ÝóáõÙ:



S. Darbinyan and I. Karapetyan 3 7

Î ãàìèëüòîíîâûõ îáõîäàõ â îäíîì êëàññå
ãàìèëüòîíîâûõ îðãðàôîâ

Ñ. Äàðáèíÿí è È. Êàðàïåòÿí

Àííîòàöèÿ

Äîêàçûâàåòñÿ, ÷òî ëþáîé ñèëüíî ñâÿçíûé n-âåðøèííûé (n > 3 ) îðãðàô, êî-
òîðûé óäîâëåòâîðÿåò îäíîìó äîñòàòî÷íîìó óñëîâèþ ãàìèëüòîíîâîñòè îðãðàôîâ
(J.of Graph Theory 22(2) (1996) 181-187) è èìååò ìèíèìàëüíóþ ïîëóñòåïåíü èñõîäà
è çàõîäà íå ìåíøüå ÷åì 2 è 3, ñîîòâåòñòâåííî, ñîäåæèò ãàìèëüòîíîâûé îáõîä, ò.å.,
êîíòóð, êîòîðûé ïîëó÷àåòñÿ èç ãàìèëüòîíîâîãî êîíòóðà ïîñëå ïåðåîðèåíòàöèè
îäíîé äóãè.