02_darbinyan_18_05_2017.DVI


Mathematical Problems of Computer Science 47, 15{29, 2017.

On Cyclability of Digr aphs with a M anoussakis-type

Condition

S a m ve l K h . D a r b in ya n

Institute for Informatics and Automation Problems of NAS RA

e-mail: samdarbin@ipia.sci.am

Abstract

Let D be a digraph of order n ¸ 4 and Y be a non-empty subset of vertices of D.
Let for any pair u, v of distinct vertices of Y the digraph D contain a path from u
to v and a path from v to u. Suppose D satis¯es the following conditions for every
triple x; y; z 2 Y 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+(z) + d¡(x) ¸ 3n ¡ 2. We prove that there is a directed cycle in D
which contains all the vertices of Y , except possibly one. This result is best possible
in some situations and gives an answer to a question of Li, Flandrin and Shu (Discrete
Mathematics, 307 (2007) 1291-1297).

Keywords: Digraphs, Cycles, Hamiltonian cycles, Cyclability.

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

Fo r c o n ve n ie n c e o f t h e r e a d e r , t e r m in o lo g y a n d n o t a t io n s will b e g ive n in d e t a ils in s e c t io n
2 . A s e t S o f ve r t ic e s in a d ir e c t e d g r a p h D ( a n u n d ir e c t e d g r a p h G) is s a id t o b e c yc la b le in
D ( in G ) if D ( if G) c o n t a in s a d ir e c t e d c yc le ( u n d ir e c t e d c yc le ) t h r o u g h a ll t h e ve r t ic e s o f
S. Th e r e a r e m a n y we ll-kn o wn c o n d it io n s wh ic h g u a r a n t e e t h e c yc la b ilit y o f a s e t o f ve r t ic e s
in a n u n d ir e c t e d g r a p h . Mo s t o f t h e m c a n b e s e e n a s r e s t r ic t io n s o f H a m ilt o n ia n c o n d it io n s
t o t h e c o n s id e r e d s e t o f ve r t ic e s ( S e e [1 , 2 , 3 , 4 ]) . L e t 's p r o vid e s o m e e xa m p le s b e lo w:
T heor em A: ( R . S h i [3 ]) . L et G be a 2-connected undirected graph of order n. If S is a
subset of the vertices of G and d( x ) ¸ n= 2 for all vertices x 2 S, then S is cyclable in G.
T heor em B : ( R . S h i [3 ]) . L et G be a 2-connected undirected graph of order n. If S is a
subset of the vertices of G and d ( x) + d( y ) ¸ n for any two nonadjacent vertices x 2 S and
y 2 S, then S is cyclable in G.

N o t ic e t h a t Th e o r e m s A a n d B g e n e r a liz e t h e c la s s ic a l t h e o r e m s o n h a m ilt o n ic it y o f D ir a c
a n d Or e , r e s p e c t ive ly. 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 .

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 S b e a n o n -e m p t y s u b s e t o f ve r t ic e s o f D.
Fo llo win g [5 ], we s a y t h a t a d ig r a p h D is S-s t r o n g ly c o n n e c t e d if fo r a n y p a ir x; y o f d is t in c t
ve r t ic e s o f S t h e d ig r a p h D c o n t a in s a p a t h fr o m x t o y a n d a p a t h fr o m y t o x.

A Me yn ie l s e t M is a s u b s e t o f ve r t ic e s o f a d ig r a p h D s u c h t h a t d ( x) + d ( y ) ¸ 2 n ¡ 1
fo r e ve r y p a ir o f d is t in c t ve r t ic e s x, y in M wh ic h a r e n o n a d ja c e n t in D.

1 5



1 6 On Cyclability of Digraphs with a Manoussakis-type Condition

Fo r g e n e r a l d ir e c t e d g r a p h s ( d ig r a p h s ) t h e r e a r e n o t a s m a n y c o n d it io n s in lit e r a t u r e
a s fo r u n d ir e c t e d g r a p h s t h a t g u a r a n t e e t h e e xis t e n c e o f a d ir e c t e d c yc le wit h t h e g ive n
p r o p e r t ie s ( in p a r t ic u la r , s u ± c ie n t c o n d it io n s fo r t h e e xis t e n c e o f a H a m ilt o n ia n c yc le s in
d ig r a p h s ) . Th e m o r e g e n e r a l a n d c la s s ic a l o n e s a r e t h e fo llo win g t h e o r e m o f M. Me yn ie l:
T heor em C: ( M. Me yn ie l [6 ]) . L et D be a strongly connected digraph of order n ¸ 2 . If the
vertex set of D is a M eyniel set, then D is Hamiltonian.

N o t ic e t h a t Me yn ie l's t h e o r e m is a g e n e r a liz a t io n o f we ll-kn o wn c la s s ic a l t h e o r e m s o f
Gh o u ila -H o u r i [7 ] a n d W o o d a ll [8 ]. A b e a u t ifu l s h o r t p r o o f o f Me yn ie l's t h e o r e m c a n b e
fo u n d in [9 ] ( s e e a ls o [1 0 ], p p . 3 9 9 -4 0 0 ) .

In [1 1 ], t h e fo llo win g wa s p r o ve d :
T heor em D: ( S . D a r b in ya n [1 1 ]) . L et D be a strongly connected digraph of order n ¸ 3 and
Y be a subset of vertices of D. If jY j = n ¡ 1 and Y is a M eyniel set, then D is Hamiltonian
or contains a cycle of length n ¡ 1 .

Fr o m Th e o r e m D we o b t a in t h e fo llo win g c o r o lla r ie s .
Cor ollar y 1: L et D be a strongly connected digraph of order n ¸ 3 . If D has n ¡ 1 vertices
of degree at least n, then D is Hamiltonian or contains a cycle of length n ¡ 1 .
Cor ollar y 2: L et D be a strongly connected digraph of order n ¸ 3 and Y be a subset of
vertices of D. If jY j = n ¡ 1 and Y is a M eyniel set, then D has a cycle that contains all
the vertices of Y .

A s u ± c ie n t c o n d it io n fo r c yc la b ilit y 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
wa s g ive n b y K . A . B e r m a n a n d X . L iu [1 2 ]. Th e y im p r o ve d Th e o r e m F b y p r o vin g t h e
fo llo win g g e n e r a liz a t io n o f t h e we ll-kn o wn t h e o r e m o f Me yn ie l.
T heor em E : ( K . B e r m a n a n d X . L iu [1 2 ]) . L et D be a strongly connected digraph of order
n. Then every M eyniel set M of D lies in a directed cycle.

L a t e r H . L i, E . Fla n d r in a n d J. S h u [5 ] p r o ve d t h e fo llo win g g e n e r a liz a t io n o f Th e o r e m
E .
T heor em F: ( H . L i, E . Fla n d r in a n d J. S h u [5 ]) . L et D be a digraph of order n and M be
a M eyniel set in D. If D is M -strongly connected, then D contains a cycle through all the
vertices of M .

L e t D b e a d ig r a p h o f o r d e r n. W e s a y t h a t a n o n -e m p t y s u b s e t Y o f t h e ve r t ic e s o f
D s a t is ¯ e s c o n d it io n A0 if fo r e ve r y t r ip le o f t h e ve r t ic e s x; y; z in Y s u c h t h a t x a n d y a r e
n o n a d ja c e n t : If t h e r e is n o a r c fr o m x t o z, t h e n d ( x) + d( y ) + d+ ( x ) + d¡ ( z ) ¸ 3 n ¡ 2 . If
t h e r e is n o a r c fr o m z t o x, t h e n d( x ) + d ( y ) + d¡ ( x ) + d+ ( z ) ¸ 3 n ¡ 2 .

Y . Ma n o u s s a kis [1 3 ] p r o ve d a s u ± c ie n t c o n d it io n fo r h a m ilt o n ic it y o f d ig r a p h s t h a t in -
vo lve s t r ip le s r a t h e r t h a n p a ir s o f ve r t ic e s .
T heor em G: ( Y . Ma n o u s s a kis [1 3 ]) . L et D be a strongly connected digraph of order n ¸ 4 .
If V ( D ) satis¯es condition A0, then D is Hamiltonian.

H . L i, Fla n d r in a n d S h u [5 ] p u t a qu e s t io n t o kn o w if t h is t h e o r e m o f Ma n o u s s a kis ( o r
t h e s u ± c ie n t c o n d it io n s o f h a m ilt o n ic it y o f d ig r a p h s o f B a n g -Je n s e n , Gu t in a n d L i [1 4 ] o r o f
B a n g -Je n s e n , Gu o a n d Y e o [1 5 ]) h a s a c yc la b le ve r s io n .

In t h is p a p e r we p r o ve t h e fo llo win g t h e o r e m wh ic h g ive s s o m e a n s we r s t o t h e a b o ve
qu e s t io n wh e n a s u b s e t Y 6= ; o f t h e ve r t ic e s o f a d ig r a p h D s a t is ¯ e s c o n d it io n A0 a n d t h e
d ig r a p h D is Y -s t r o n g ly c o n n e c t e d .
T heor em 1: L et D be a digraph of order n ¸ 4 and let Y be a non-empty subset of the
vertices of D. Suppose that D is Y -strongly connected and the subset Y satis¯es condition
A0. Then D contains a cycle through all the vertices of Y maybe except one.
Remar k 1: The following example shows that there is a digraph D which contains a



S. Darbinyan 1 7

nonempty subset Y of V ( D ) such that D is Y -strongly connected and the subset Y satis-
¯es condition A0 but D has no cycle that contains all the vertices of Y .

To s e e t h is , le t G a n d H b e t wo a r b it r a r y d is jo in t d ig r a p h s wit h jV ( G ) j = m ¸ 2 a n d
jV ( H ) j = n ¡ m ¸ 4 . L e t y 2 V ( H ) a n d x; z 2 V ( G ) , x 6= z. A s s u m e t h a t d( y; H ) =
2 ( n ¡ m ¡ 1 ) , G c o n t a in s a H a m ilt o n ia n c yc le , d+ ( x; G) = m ¡ 1 a n d d( z; G ) = 2 ( m ¡ 1 ) .
Fr o m G a n d H we fo r m a n e w d ig r a p h D wit h V ( D ) = V ( G ) [ V ( H ) a s fo llo ws : a d d a ll t h e
p o s s ib le a r c s ux; xu, wh e r e u 2 V ( H ) n fyg, a n d t h e a r c yx. A n e a s y c o m p u t a t io n s h o ws
t h a t

d( y ) + d( z ) + d¡ ( y ) + d+ ( x) = 4 n ¡ m ¡ 6 ¸ 3 n ¡ 2 ;

s in c e m · n ¡ 4 . Th u s , we h a ve t h a t t h e s e t Y = fx; y; zg s a t is ¯ e s c o n d it io n A0. D is
Y -s t r o n g ly c o n n e c t e d a n d h a s n o c yc le t h a t c o n t a in s a ll t h e ve r t ic e s o f Y .

Ou r p r o o fs a r e b a s e d o n t h e a r g u m e n t s o f [5 , 1 3 ].

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

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 . Te r m in o lo g y a n d
n o t a t io n s n o t d e s c r ib e d b e lo w fo llo w [1 6 ]. Th e ve r t e x s e t a n d t h e a r c s e t o f a d ig r a p h D
a r e d e n o t e d b y V ( D ) a n d A ( D ) , r e s p e c t ive ly. 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 .
Fo r a n y x; y 2 V ( D ) , we a ls o wr it e x ! y if xy 2 A ( D ) . If xy 2 A ( D ) , t h e n we s a y t h a t x
d o m in a t e s y o r y is a n o u t -n e ig h b o u r o f x a n d x is a n in -n e ig h b o u r o f y. If x ! y a n d y ! z
we wr it e x ! y ! z. 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 ) . If t h e r e is n o a r c fr o m x t o y we s h a ll u s e t h e n o t a t io n xy =2 A ( D ) .

W e le t N + ( x ) , N¡ ( x ) d e n o t e t h e s e t o f o u t -n e ig h b o u r s , r e s p e c t ive ly t h e s e t o f in -
n e ig h b o u r s o f a ve r t e x x in a d ig r a p h D. If A µ V ( D ) , t h e n N + ( x; A) = A \ N + ( x )
a n d N¡ ( x; A ) = A \ N¡ ( x) . 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. If x 2 V ( D )
a n d A = fxg we s o m e t im e s wr it e x in s t e a d o f fxg. 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 s u b d ig r a p h o f D
in d u c e d b y a s u b s e t A o f V ( D ) is d e n o t e d b y DhAi o r hAi fo r b r e vit y.

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, x1x2 ¢ ¢ ¢ xmx1 ) . Th e le n g t h o f a c yc le o r p a t h is t h e
n u m b e r o f it s a r c s . 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 .
A n ( x; y ) -p a t h P is a n ( X; Y ) -p a t h if x 2 X, y 2 Y a n d V ( P ) \ ( X [ Y ) = fx; yg, wh e r e X
a n d Y a r e s o m e s u b s e t s o f t h e ve r t ic e s o f a d ig r a p h D.

Give n a ve r t e x x o f a d ir e c t e d p a t h P o r a d ir e c t e d c yc le C, we u s e t h e n o t a t io n s x+ a n d
x¡ fo r t h e s u c c e s s o r a n d t h e p r e d e c e s s o r o f x ( o n P o r o n C ) a c c o r d in g t o t h e o r ie n t a t io n
a n d in c a s e o f a m b ig u it y, we p r e c is e P o r C a s a s u b s c r ip t ( t h a t is x+P ...) .

A c yc le ( r e s p e c t ive ly, a p a t h ) t h a t c o n t a in s a ll t h e ve r t ic e s o f D is a H a m ilt o n ia n c yc le
( r e s p e c t ive ly, is a H a m ilt o n ia n p a t h ) . A d ig r a p h 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 . Fo r a c yc le C := 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. If C is a c yc le a n d P is a p a t h in a d ig r a p h
D, o ft e n we will wr it e C in s t e a d o f V ( C ) a n d P in s t e a d o f V ( P ) . A d ig r a p h D is s t r o n g ly



1 8 On Cyclability of Digraphs with a Manoussakis-type Condition

c o n n e c t e d ( o r , ju s t , s t r o n g ) if t h e r e e xis t s a p a t h fr o m x t o y a n d a p a t h fr o m y t o x fo r
e ve r y p a ir o f d is t in c t ve r t ic e s x; y.

L e t C b e a n o n -H a m ilt o n ia n c yc le in a d ig r a p h D. Fo r t h e c yc le C, a C-b yp a s s is a p a t h
o f le n g t h a t le a s t t wo wit h b o t h e n d -ve r t ic e s o n C a n d n o o t h e r ve r t ic e s o n C. If ( x; y ) -p a t h
P is a C-b yp a s s wit h V ( P ) \ V ( C ) = fx; yg, t h e n we c a ll t h e le n g t h o f t h e p a t h C[x; y] t h e
g a p o f P wit h r e s p e c t t o C.

If we c o n s id e r a s u b s e t o f ve r t ic e s S µ V ( D ) , we d e n o t e t h e ve r t ic e s o f S b y S-ve r t ic e s
a n d t h e n u m b e r o f S-ve r t ic e s in a c yc le is c a lle d it s S-le n g t h .

Th e s u b d ig r a p h o f a d ig r a p h D in d u c e d b y a s u b s e t A o f V ( D ) is d e n o t e d b y DhAi, o r
hAi fo r b r e vit y. Th e c o n ve r s e d ig r a p h o f a d ig r a p h D is t h e d ig r a p h o b t a in e d fr o m D b y
r e ve r s in g a ll a r c s o f D.

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.

3 . P r e lim in a r ie s

W e n o w c o lle c t t h e t o o ls wh ic h we n e e d in p r o o f o f o u r t h e o r e m . In t h e fo llo win g , we o ft e n
u s e t h e fo llo win g d e ¯ n it io n :
De¯nition 1: L et P = x1x2 : : : xm (m ¸ 2 ) be a path in a digraph D and Q = y1y2 : : : yk be
a path in hV ( D ) n V ( P ) i (possibly, k = 1 ). Assume that there is an i 2 [1 ; m ¡ 1 ] such that
xiy1 and ykxi+1 2 A( D ) . In this case D contains the path x1x2 : : : xiy1y2 : : : ykxi+1 : : : xm and
we say that Q can be inserted into P .

Th e fo llo win g L e m m a s 1 a n d 2 a r e s lig h t ly m o d i¯ e d ve r s io n s o f le m m a b y H Äa g g kvis t a n d
Th o m a s [1 7 ] a n d o f le m m a b y B o n d y a n d Th o m a s s e n [9 ], r e s p e c t ive ly ( t h e ir p r o o fs a r e n o t
t o o d i± c u lt ) . Th e y will b e u s e d e xt e n s ive ly in t h e p r o o f o f o u r r e s u lt .
Lemma 1: L et Ck := x1x2 : : : xkx1, k ¸ 2 , be a non-Hamiltonian cycle in a digraph D.
M oreover, assume that there exists a path Q := y1y2 : : : yr, r ¸ 1 , in hV ( D ) n V ( Ck ) i. If
d¡ ( y1; Ck ) + d

+ ( yr; Ck ) ¸ k + 1 , then for all m 2 [r + 1 ; k + r] the digraph D contains a cycle
Cm of length m with vertex set V ( Cm ) µ V ( Ck ) [ V ( Q) .
Lemma 2: L et P := x1x2 : : : xk, k ¸ 2 , be a non-Hamiltonian path in a digraph D. M ore-
over, assume that there exists a path Q := y1y2 : : : yr, r ¸ 1 , in hV ( D ) n V ( P ) i. If

d¡ ( y1; P ) + d
+ ( yr; P ) ¸ k + d¡ ( y1; fxkg) + d+ ( yr; fx1g ) ;

then there is an i 2 [1 ; k ¡ 1 ] such that xiy1 and yrxi+1 2 A ( D ) , i.e., D contains a path from
x1 to xk with vertex set V ( P ) [ V ( Q ) , i.e., Q can be inserted into P .

Th e fo llo win g le m m a fr o m [5 ] is a s lig h t ly m o d ī e d ve r s io n o f Mu lt i-In s e r t io n L e m m a
d u e t o B a n g -Je n s e n , Gu t in a n d H . L i ( s e e [1 6 ], L e m m a 5 .6 .2 0 ) .
Lemma 3: ( H . L i, E . Fla n d r in . J. S h u [5 ]) . L et D be a digraph and let P be an ( a; b ) -path in
D. L et Q be a path in hV ( D ) n V ( P ) i and S be a subset of V ( Q ) . If every vertex of S can be
inserted into P , then there exists an ( a; b ) -path R such that V ( P ) [S µ V ( R) µ V ( P ) [V ( Q ) .

Th e fo llo win g le m m a a ls o wa s p r o ve d in [5 ].
Lemma 4: ( H . L i, E . Fla n d r in . J. S h u [5 ]) . L et D be a digraph of order n and S ½ V ( D ) ,
S 6= ; be a M eyniel set. Assume that D is S-strongly connected and C is a cycle in D of
maximum S-length. If s is an S-vertex of V ( D ) n V ( C ) , then D contains a C-bypass through
s.

B y t h e in s p e c t io n o f t h e p r o o f in [1 2 ] o n e c a n s t a t e L e m m a 4 in t h e fo llo win g fo r m ( it s
p r o o f is t h e s a m e a s t h e p r o o f o f L e m m a 4 ) .



S. Darbinyan 1 9

Lemma 5: L et D be a digraph of order n and C be a non-Hamiltonian cycle in D. L et x be
an arbitrary vertex not on this cycle C and D contain no C-bypass through x. If in D there
are ( C; x ) - and ( x; C ) -paths, then the following holds:

(i). If x is adjacent to some vertex y of C, then D is not 2-strong, d ( x; V ( C ) n fyg ) = 0
and d( x ) + d( z ) · 2 n ¡ 2 for all vertices z 2 V ( C ) n fyg.

(ii). Assume that x and any vertex of C are nonadjacent, i.e., d ( x; V ( C ) ) = 0 . L et
P be a shortest ( C; x ) -path with fug = V ( P ) \ V ( C ) and Q be a shortest ( x; C ) -path with
fvg = V ( Q ) \ V ( C ) (possibly, u = v). Then d( x ) + d( z ) · 2 n ¡ 2 for all vertices z 2 V ( C ) ,
maybe except one from fu; vg.

In [1 3 ], t h e fo llo win g wa s p r o ve d :
Lemma 6: ( Y . Ma n o u s s a kis [1 3 ]) . L et D be a digraph of order n and V ( D ) satisfy condition
A0. Assume that there are two distinct pairs of nonadjacent vertices x; y and x; z in D. Then
either d( x ) + d( y ) ¸ 2 n ¡ 1 or d ( x) + d ( z ) ¸ 2 n ¡ 1 .

It is n o t d i± c u lt t o s h o w t h a t we c a n s t a t e L e m m a 6 in t h e fo llo win g m u c h s t r o n g e r
fo r m :
Lemma 7: L et D be a digraph of order n and Y be a subset of V ( D ) . Assume that Y
satis¯es condition A0 and contains two distinct pairs of nonadjacent vertices x; y and x; z.
Then either d( x ) + d( y ) ¸ 2 n ¡ 1 or d ( x) + d ( z ) ¸ 2 n ¡ 1 .

Fo r t h e p r o o f o f o u r r e s u lt we a ls o n e e d t h e fo llo win g s im p le le m m a .
Lemma 8: L et D be a digraph of order n. Assume that xy =2 A( D ) and the vertices x, y in
D satisfy the degree condition d+ ( x ) + d¡ ( y ) ¸ n ¡ 2 + k, where k ¸ 1 . Then D contains at
least k internally disjoint ( x; y ) -paths of length two.

Th e fo llo win g le m m a a ls o wa s p r o ve d in [5 ].
Lemma 9: ( H . L i, E . Fla n d r in . J. S h u [5 ]) . L et D be a digraph of order n and S µ V ( D ) ,
S 6= ; be a M eyniel set. If D is S-strongly connected, then any two S-vertices s and s0 are
contained in a cycle of D such that they are at distance at most two on this cycle.

W e c a n s t a t e L e m m a 9 in t h e fo llo win g fo r m .
Lemma 10: L et D be a digraph of order n. Assume that a pair of distinct vertices x; y in
D satis¯es the degree condition d( x ) + d( y ) ¸ 2 n ¡ 1 . If D is fx; yg-strongly connected, then
the vertices x and y are contained in a cycle of D such that they are at distance at most two
on this cycle.

N o w we will p r o ve t h e fo llo win g le m m a .
Lemma 11: L et D be a digraph of order n and Y be a subset of vertices of D with jY j ¸ 4 .
Assume that D is Y -strongly connected and the subset Y satis¯es condition A0. If C is a
non-Hamiltonian cycle in D which contains at least two Y -vertices and y 2 V ( D ) n V ( C ) is
an arbitrary Y -vertex, then D contains a C-bypass through y.
P r oof of Lemma 11. If t h e c yc le C c o n t a in s a t le a s t t h r e e Y -ve r t ic e s , t h e n t h e le m m a
im m e d ia t e ly fo llo ws fr o m L e m m a s 5 a n d 7 . W e m a y t h e r e fo r e a s s u m e t h a t C c o n t a in s e xa c t ly
t wo Y -ve r t ic e s , s a y x a n d u, a n d t h e r e e xis t s a Y -ve r t e x, s a y y, in B := V ( D ) n V ( C ) s u c h
t h a t in D t h e r e is n o C-b yp a s s t h r o u g h y. Fr o m jY j ¸ 4 it fo llo ws t h a t B c o n t a in s a t le a s t
t wo Y -ve r t ic e s . L e t z b e a n a r b it r a r y Y -ve r t e x in B o t h e r t h a n y.

W e will c o n s id e r t wo c a s e s d e p e n d in g u p o n t h e va lu e o f d( y; C ) .
Case 1: d( y; C ) ¸ 1 .
W it h o u t lo s s o f g e n e r a lit y, a s s u m e t h a t t h e ve r t e x y is a d ja c e n t t o a ve r t e x w o f V ( C ) .

If w =2 fu; xg, t h e n fr o m L e m m a 5 ( i) it fo llo ws t h a t y; u a n d y; x a r e d is t in c t p a ir s o f
n o n a d ja c e n t ve r t ic e s o f Y , d( y ) + d ( u) · 2 n ¡ 2 a n d d( y ) + d ( x) · 2 n ¡ 2 , wh ic h c o n t r a d ic t s



2 0 On Cyclability of Digraphs with a Manoussakis-type Condition

L e m m a 7 . W e m a y t h e r e fo r e a s s u m e t h a t w 2 fx; ug, fo r e xa m p le , le t w = u a n d yu 2 A( D ) .
S in c e we a s s u m e d t h a t D h a d n o C-b yp a s s t h r o u g h y, b y L e m m a 5 ( i) we h a ve

d ( y ) + d ( x) · 2 n ¡ 2 a n d d( y; V ( C ) n fug ) = 0 : ( 1 )

N o w we c o n s id e r t wo s u b c a s e s xz 2 A( D ) , xz =2 A ( D ) .
Subcase 1.1. xz 2 A( D ) .
Th e n zy =2 A ( D ) ( fo r o t h e r wis e , xzyu is a C-b yp a s s t h r o u g h y, wh ic h c o n t r a d ic t s o u r

a s s u m p t io n t h a t D h a s n o C-b yp a s s t h r o u g h y ) . Th e r e fo r e , t h e t r ip le o f Y -ve r t ic e s x; y; z
s a t is ¯ e s c o n d it io n A0, i.e .,

d( y ) + d( x ) + d¡ ( y ) + d+ ( z ) ¸ 3 n ¡ 2 :

Th is t o g e t h e r wit h d( y ) + d ( x) · 2 n ¡ 2 ( b y ( 1 ) ) im p ly t h a t d+ ( z ) + d¡ ( y ) ¸ n. H e n c e , b y
L e m m a 8 , z ! v ! y fo r s o m e ve r t e x v o t h e r t h a n u. Fr o m d( y; V ( C ) n fug) = 0 ( b y ( 1 ) )
it fo llo ws t h a t v 2 B. Th u s , xzvyu is a C-b yp a s s t h r o u g h y, a c o n t r a d ic t io n .

Subcase 1.2. xz =2 A( D ) .
Th e n b y c o n d it io n A0 we h a ve

d( y ) + d( x ) + d+ ( x) + d¡ ( z ) ¸ 3 n ¡ 2 :

Th e r fo r e , b y ( 1 ) , d+ ( x ) + d¡ ( z ) ¸ n, a n d h e n c e b y L e m m a 8 a n d xy =2 A ( D ) , t h e r e e xis t s
a ve r t e x v o t h e r t h a n u a n d y s u c h t h a t x ! v ! z. It is e a s y t o s e e t h a t vy =2 A ( D )
a n d zy =2 A ( D ) . In t h is s u b c a s e , a g a in we h a ve t h a t d+ ( z ) + d¡ ( y ) ¸ n. H e n c e , b y L e m m a
8 , z ! a ! y fo r s o m e ve r t e x a o t h e r t h a n u a n d v. B y ( 1 ) , a =2 V ( C ) . Th e r e fo r e , a 2
B n fy; z; vg a n d vzayu o r xvzayu is a C-b yp a s s t h r o u g h y wh e n v 2 C o r n o t , r e s p e c t ive ly,
a c o n t r a d ic t io n . Th e d is c u s s io n o f Ca s e 1 is c o m p le t e d .

Case 2: d ( y; C ) = 0 .
B y L e m m a 5 ( ii) , we h a ve e it h e r d( y ) + d( x ) · 2 n ¡ 2 o r d ( y ) + d ( u ) · 2 n ¡ 2 . W it h o u t

lo s s o f g e n e r a lit y, a s s u m e t h a t
d( y ) + d( x ) · 2 n ¡ 2 : ( 2 )

Th is t o g e t h e r wit h c o n d it io n A0 im p ly t h a t

d+ ( y ) + d¡ ( u ) ¸ n a n d d+ ( u ) + d¡ ( y ) ¸ n: ( 3 )

Th is t o g e t h e r wit h L e m m a 8 im p ly t h a t t h e r e a r e ve r t ic e s a a n d v ( p o s s ib ly, a = v ) o t h e r
t h a n z s u c h t h a t u ! v ! y a n d y ! a ! u. Ob s e r ve t h a t v a n d a a r e n o t o n C s in c e
d( y; C ) = 0 .

Fir s t c o n s id e r t h e c a s e d( z; V ( C ) n fug ) 6= 0 . W it h o u t lo s s o f g e n e r a lit y, a s s u m e t h a t
w 2 V ( C ) n fug a n d zw 2 A ( D ) ( fo r t h e c a s e wz 2 A ( D ) we will c o n s id e r t h e c o n ve r s e
d ig r a p h o f D ) . If yz 2 A ( D ) , t h e n uvyzw is a C-b yp a s s t h r o u g h y, a c o n t r a d ic t io n . W e
m a y t h e r e fo r e a s s u m e t h a t yz =2 A ( D ) . Th e n fr o m ( 2 ) a n d c o n d it io n A0 it fo llo ws t h a t
d+ ( y ) + d¡ ( z ) ¸ n. Th e r e fo r e , b y L e m m a 8 , fo r s o m e ve r t e x b 2 B n fvg, y ! b ! z, a n d
h e n c e , uvybzw is a C-b yp a s s t h r o u g h y, wh ic h is a c o n t r a d ic t io n .

N o w c o n s id e r t h e c a s e d ( z; V ( C ) n fug) = 0 . Th e n t h e ve r t ic e s z a n d x a r e n o n a d ja c e n t .
Fr o m ( 2 ) a n d c o n d it io n A0 it fo llo ws t h a t

d+ ( x ) + d¡ ( z ) ¸ n a n d d+ ( z ) + d¡ ( x ) ¸ n:



S. Darbinyan 2 1

Fr o m d+ ( z ) + d¡ ( x ) ¸ n a n d L e m m a 8 it fo llo ws t h a t t h e r e a r e a t le a s t t wo ( z; x ) -p a t h s
o ft h e le n g t h t wo .

Subcase 2.1. There is a ( z; x ) -paths of the length two, say z ! b ! x, such that b =2 fu; vg.
In t h is s u b c a s e , yz =2 A ( D ) a n d yb =2 A( D ) ( fo r o t h e r wis e , uvyzbx o r uvybx is a C-b yp a s s

t h r o u g h y, fo r yz 2 A( D ) a n d fo r yb 2 A ( D ) , r e s p e c t ive ly) . S in c e x; y; z a r e Y -ve r t ic e s , fr o m
c o n d it io n A0 a n d ( 2 ) it fo llo ws t h a t d

+ ( y ) + d¡ ( z ) ¸ n. N o w u s in g L e m m a 8 a n d t h e fa c t s
t h a t yz =2 A ( D ) a n d yb =2 A( D ) , we o b t a in t h a t t h e r e e xis t s a ve r t e x q 2 B n fv; b; zg s u c h
t h a t y ! q ! z. Th u s , uvyqzbx is a C-b yp a s s t h r o u g h y, a c o n t r a d ic t io n .

Subcase 2.2. There is no w 2 B n fvg such that z ! w ! x.
Th e n fr o m L e m m a 8 a n d d+ ( z ) + d¡ ( x ) ¸ n it fo llo ws t h a t d+ ( z ) + d¡ ( x) = n a n d

zv; vx; zu 2 A( D ) ( i.e ., t h e r e a r e e xa c t ly t wo ( z; x ) -p a t h s o f t h e le n g t h t wo ) . N o w u s in g t h e
in e qu a lit y d+ ( u ) +d¡ ( y ) ¸ n ( b y ( 3 ) ) a n d L e m m a 8 we c o n c lu d e t h a t t h e r e e xis t a t le a s t t wo
( u; y ) -p a t h s o f t h e le n g t h t wo . If t h e r e is a p a t h u ! c ! y s u c h t h a t c is o t h e r t h a n v a n d
z, t h e n we m a y c o n s id e r t h e p a t h s u ! c ! y a n d z ! v ! x. Fo r t h e s e p a t h s we h a ve t h e
a b o ve c o n s id e r e d c a s e ( b =2 fu; vg) . W e m a y t h e r e fo r e a s s u m e t h a t t h e r e is n o c 2 B n fv; zg
s u c h t h a t u ! c ! y. Fr o m t h is a n d L e m m a 8 it fo llo ws t h a t d+ ( u ) + d¡ ( y ) = n a n d
u ! z ! y s in c e d+ ( u ) + d¡ ( y ) ¸ n ( b y ( 3 ) ) . Th is t o g e t h e r wit h vx 2 A ( D ) im p ly t h a t
yv =2 A( D ) ( if yv 2 A ( D ) , t h e n uzyvx is a C-b yp a s s t h r o u g h y ) . N o w b y c o n d it io n A0 a n d
( 2 ) we h a ve

d( y ) + d ( x) = 2 n ¡ 2 ;
s in c e x; y; u a r e Y -ve r t ic e s , x; y a r e n o t a d ja c e n t a n d uy =2 A( D ) . Th e la s t e qu a lit y im p lie s
t h a t d+ ( y ) + d¡ ( x ) ¸ n ¡ 1 o r d¡ ( y ) + d+ ( x) ¸ n ¡ 1 .

If d+ ( y ) +d¡ ( x ) ¸ n¡ 1 , t h e n , s in c e yv =2 A ( D ) a n d d ( y; C ) = 0 , fr o m L e m m a 8 it fo llo ws
t h a t t h e r e e xis t s a ve r t e x z1 2 Bnfvg s u c h t h a t y ! z1 ! x. Th e r e fo r e , uvyz1x is a C-b yp a s s
t h r o u g h y, a c o n t r a d ic t io n . W e m a y t h e r e fo r e a s s u m e t h a t d+ ( y ) + d¡ ( x ) · n ¡ 2 . Th e n
d¡ ( y ) +d+ ( x) ¸ n s in c e d ( y ) +d( x ) = 2 n¡ 2 . Th e r e fo r e , s in c e d( y; C ) = d( z; V ( C ) nfug ) = 0 ,
b y L e m m a 8 t h e r e e xis t s a ve r t e x z2 2 B n fag s u c h t h a t x ! z2 ! y. H e n c e , xz2yau is
a C-b yp a s s t h r o u g h y, wh ic h is 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 c o m p le t e s t h e p r o o f o f
L e m m a 1 1 .

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

Fo r r e a d e r s c o n ve n ie n c e , a g a in we will fo r m u la t e t h e m a in r e s u lt .
T heor em 1: L et D be a digraph of order n and let Y be a nonempty subset of the vertices
of D, where jY j ¸ 2 . Suppose that D is Y -strongly connected and the subset Y satis¯es
condition A0. Then D contains a cycle through all the vertices of Y maybe except one.
P r oof: If jY j = 2 , t h e n t h e r e is n o t h in g t o p r o ve . If jY j = 3 , t h e n fr o m Y -s t r o n g ly
c o n n e c t e d n e s s o f D it fo llo ws t h a t Y is a n in d e p e n d e n t s e t . B y L e m m a 7 , fo r s o m e t wo
ve r t ic e s o f Y , s a y x a n d y, we h a ve d( x ) + d ( y ) ¸ 2 n ¡ 1 . Th e r e fo r e , b y L e m m a 1 0 , t h e r e
is a c yc le in D t h a t c o n t a in s t h e ve r t ic e s x a n d y. In t h e s e qu e l, a s s u m e t h a t jY j ¸ 4 .
N o w s u p p o s e t h a t t h e s u b s e t Y o f t h e ve r t ic e s o f D s a t is ¯ e s t h e s u p p o s it io n o f t h e t h e o r e m
b u t a n y c yc le in D d o e s n o t c o n t a in a t le a s t t wo Y -ve r t ic e s . B y Ma n o u s s a kis ' t h e o r e m , we
m a y a s s u m e t h a t Y 6= V ( D ) . S in c e D is Y -s t r o n g ly c o n n e c t e d , u s in g L e m m a s 7 a n d 1 0
we o b t a in t h a t in D t h e r e e xis t s a c yc le wh ic h c o n t a in s a t le a s t t wo Y -ve r t ic e s . If C is a
n o n -H a m ilt o n ia n c yc le in D wh ic h c o n t a in s a t le a s t t wo Y -ve r t ic e s a n d y 2 V ( D ) n V ( C ) is
a n a r b it r a r y Y -ve r t e x, t h e n fr o m L e m m a 1 1 it fo llo ws t h a t D c o n t a in s a C-b yp a s s t h r o u g h



2 2 On Cyclability of Digraphs with a Manoussakis-type Condition

y. In D we c h o o s e a c yc le C a n d a C-b yp a s s P0 t h r o u g h a Y -ve r t e x o f V ( D ) n V ( C ) s u c h
t h a t

( a ) C c o n t a in s a s m a n y ve r t ic e s o f Y a s p o s s ib le ( C c o n t a in s a t le a s t t wo Y -ve r t ic e s ) ,
( b ) t h e g a p o f C-b yp a s s P0 is m in im u m , s u b je c t t o ( a ) ( b y L e m m a 1 1 , fo r t h e c yc le C

t h e r e e xis t s a C-b yp a s s t h r o u g h a n y Y -ve r t e x n o t o n C ) , a n d
( c ) t h e le n g t h o f C-b yp a s s P0 is m in im u m , s u b je c t t o ( a ) a n d ( b ) .
In t h e s e qu e l we a s s u m e t h a t t h e c yc le C := x1x2 : : : xmx1 a n d t h e C-b yp a s s P0 :=

x1z1 : : : zkyzk+1 : : : ztxa+1 s a t is fy t h e c o n d it io n s ( a ) -( c ) , wh e r e 1 · a · m ¡ 1 a n d y 2
V ( D ) n V ( C ) is a Y -ve r t e x ( p o s s ib ly, z1 = y o r y = zt ) . S in c e t h e c yc le C h a s t h e m a xim u m
Y -le n g t h , it fo llo ws t h a t a ¸ 2 a n d C[x2; xa] c o n t a in s a Y -ve r t e x. N o t e t h a t t h e g a p o f
C-b yp a s s P0 is e qu a l t o a.

D e n o t e P := z1 : : : zkyzk+1 : : : zt, E := P [z1; zk] a n d L := P [zk+1; zt]. S in c e t h e g a p a
is m in im a l, t h e ve r t e x y is n o t a d ja c e n t t o a n y ve r t e x o f C[x2; xa], i.e , d( y; C[x2; xa]) = 0 .
Th e r e fo r e , b y L e m m a 2 ,

d( y; C ) = d( y; C[xa+1; x1]) · m ¡ a + d¡ ( y; fx1g ) + d+ ( y; fxa+1g ) ; ( 4 )

s in c e a n y Y -ve r t e x o f B := V ( D ) n V ( C ) c a n n o t b e in s e r t e d in t o C. Fr o m t h e m in im a lit y o f
t h e p a t h P it fo llo ws t h a t

d( y; V ( P ) ) · jV ( P ) j + 1 ¡ d¡ ( y; fx1g ) ¡ d+ ( y; fxa+1g ) : ( 5 )

N o t ic e t h a t jC[x2; xa]j = a ¡ 1 a n d jC[xa+1; x1]j = m ¡ a + 1 . Fir s t ly fo r t h e c yc le C a n d
C-b yp a s s P0 := x1z1 : : : zkyzk+1 : : : ztxa+1 we p r o ve t h e fo llo win g t wo c la im s .
Claim 1: There is a Y -vertex, say y1, in C[x2; xa] such that y; y1 are nonadjacent, d( y ) +
d( y1 ) · 2 n ¡ 2 and y1 cannot be inserted into C[xa+1; x1]. M oreover,

(i). The path P contains exactly one Y -vertex, namely only y.
(ii). Any Y -vertex of C[x2; xa] other than y1 can be inserted into C[xa+1; x1].
(iii). There are three ( xa+1; x1 ) -paths, say P1; P2 and P3, with vertex set C[xa+1; x1] [ F1,

C[xa+1; x1] [ F2 and C[xa+1; x1] [ F3, respectively, where F1 µ C[x2; xa], F2 µ C[x2; y¡1 ],
F3 µ C[y+1 ; xa] ( if y1 = x2, then C[x2; y¡1 ] = ;, if y1 = xa, then C[y+1 ; xa] = ; ) and F1
( respectively, F2; F3 ) contains all the Y -vertices of C[x2; xa] n fy1g ( respectively, all the
Y -vertices of C[x2; y

¡
1 ], all the Y -vertices of C[y

+
1 ; xa]) .

P r oof: S in c e we a s s u m e d t h a t t h e c yc le C h a s m a xim u m Y -le n g t h , fr o m L e m m a 3 it fo llo ws
t h a t s o m e Y -ve r t e x, s a y y1, o f C[x2; xa] c a n n o t b e in s e r t e d in t o C[xa+1; x1]. H e n c e , u s in g
L e m m a 2 , we o b t a in

d( y1; C ) = d( y1; C[x2; xa]) + d( y1; C[xa+1; x1]) · 2 a ¡ 4 + m ¡ a + 2 = m + a ¡ 2 : ( 6 )

Fr o m t h e m in im a lit y o f C[x2; xa] it fo llo ws t h a t t h e ve r t ic e s y a n d y1 a r e n o n a d ja c e n t .
P u t R := V ( D ) n ( V ( C ) [ V ( P ) ) . N o w we wa n t t o c o m p u t e t h e s u m o f d e g r e e y a n d y1.

B y m in im a lit y o f C[x2; xa] we h a ve

d ( y1; R) + d ( y; R ) · 2 jRj a n d d( y; C[x2; xa]) = 0 : ( 7 )

Fr o m t h e m in im a lit y o f C[x2; xa] a ls o it fo llo ws t h a t

d+ ( y1; fz1; : : : ; zkg ) = d¡ ( y1; fzk+1; : : : ; ztg ) = 0 : ( 8 )



S. Darbinyan 2 3

Th e r e fo r e , d( y1; P ) · jP j ¡ 1 s in c e y a n d y1 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 t h e a b o ve
in e qu a lit ie s ( 4 ) -( 7 ) g ive

d ( y ) + d ( y1 ) = d( y; R ) + d( y1; R) + d ( y; P ) + d ( y; C ) + d( y1; P ) + d ( y1; C )

· 2 jRj + 2 jP j + 2 m ¡ 2 = 2 n ¡ 2 :
Th u s , d( y ) +d( y1 ) · 2 n¡ 2 fo r a n y Y -ve r t e x y o f P a n d fo r a n y Y -ve r t e x y1 o f C[x2; xa] wh ic h
c a n n o t b e in s e r t e d in t o C[xa+1; x1]. Th is t o g e t h e r wit h L e m m a 7 im p ly t h a t P c o n t a in s o n ly
o n e Y -ve r t e x, n a m e ly y, a n d a n y Y -ve r t e x o f C[x2; xa] d i®e r e n t fr o m y1 c a n b e in s e r t e d in t o
C[xa+1; x1]. Fr o m t h is a n d L e m m a 3 it im m e d ia t e ly fo llo ws t h e t h ir d a s s e r t io n o f t h e c la im .
Cla im 1 is p r o ve d .

B y Cla im 1 , we h a ve
d ( y1 ) + d( y ) · 2 n ¡ 2 : ( 9 )

Claim 2: L et y1 be a Y -vertex of C[x2; xa] which cannot be inserted into C[xa+1; x1]. Then
d( y1; P ) = 0 .
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( y1; P ) ¸ 1 . Th e n fr o m ( 8 ) it fo llo ws t h a t e it h e r
ziy1 2 A ( D ) o r y1zj 2 A ( D ) , fo r s o m e i 2 [1 ; k] o r j 2 [k+1 ; t], r e s p e c t ive ly. L e t y1zj 2 A ( D ) .
W e c o n s id e r t h e c yc le C1 := P3C[x1; y1]P [zj; zt]xa+1. Th is c yc le c o n t a in s a ll t h e Y -ve r t ic e s
o f C, a n d h e n c e , h a s m a xim u m Y -le n g t h . It is e a s y t o s e e t h a t Q := x1z1 : : : zkyzk+1 : : : zj is
a C1-b yp a s s t h r o u g h y. B y t h e c h o ic e o f t h e c yc le C a n d C-b yp a s s P0 we h a ve t h a t y1 = xa,
i.e ., t h e C-g a p o f P0 a n d C1-g a p o f Q a r e e qu a l b u t t h e p a t h z1 : : : zkyzk+1 : : : zj¡1 is s h o r t e r
t h a n t h e p a t h z1 : : : zkyzk+1 : : : zt, wh ic h c o n t r a d ic t s ( c ) . Th e r e fo r e , y1zj =2 A ( D ) fo r a ll
j 2 [k + 1 ; t]. S im ila r ly, we c a n p r o ve t h a t ziy1 =2 A ( D ) fo r a ll i 2 [1 ; k]. Th u s ,

d¡ ( y1; fz1; : : : ; zkg ) = d+ ( y1; fzk+1; : : : ; ztg ) = 0

wh ic h t o g e t h e r wit h ( 8 ) im p ly t h a t d ( y1; P ) = 0 . Cla im 2 is p r o ve d .
L e t x b e a n a r b it r a r y Y -ve r t e x in B = V ( D ) n V ( C ) o t h e r t h a n y. Cla im 1 ( i) im p lie s

t h a t x is n o t o n P . W e d is t in g u is h t wo c a s e s a c c o r d in g a s in hB n ( P n fyg ) i t h e r e e xis t s a
p a t h wit h e n d -ve r t ic e s x a n d y o r n o t .
Case 1: In hB n ( P n fyg ) i there exists a path from x to y or there exists a path from y to x.

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 in hB n ( P n fyg ) i t h e r e is a n ( x; y ) -p a t h
( fo r o t h e r wis e , we c o n s id e r t h e c o n ve r s e d ig r a p h o f D ) .

L e t H b e a s h o r t e s t ( x; y ) -p a t h in hB n ( P n fyg ) i. Ob s e r ve t h a t x1x =2 A ( D ) , s in c e
o t h e r wis e , if x1x 2 A ( D ) , t h e n t h e p a t h P1 ( Cla im 1 ( iii) ) t o g e t h e r wit h t h e a r c x1x a n d t h e
p a t h s H a n d P0[y; xa+1] fo r m s a c yc le , s a y C1, wh ic h c o n t a in s m o r e Y -ve r t ic e s t h a n C, wh ic h
c o n t r a d ic t s o u r a s s u m p t io n t h a t C h a s m a xim u m Y -le n g t h ( C1 c o n t a in s a ll Y -ve r t ic e s o f C,
e xc e p t y1, b u t c o n t a in s Y -ve r t ic e s x a n d y ) .

P u t R0 := B n ( V ( P ) [ V ( H ) ) a n d H0 := H[x+H ; y¡H ] ( if x+H = y, t h e n H0 = ; ) .
Fr o m t h e m in im a lit y o f t h e g a p a ( o r o f t h e e xis t e n c e o f t h e p a t h P3 ) it fo llo ws t h a t

y1x =2 A ( D ) ( t h e r e fo r e e it h e r xy1 2 A( D ) o r x a n d y1 a r e n o n a d ja c e n t ) a n d

d+ ( y1; R0 ) + d
¡ ( x; R0 ) · jR0j: ( 1 0 )

Subcase 1.1. xy1 2 A ( D ) .
Fr o m L e m m a 2 it fo llo ws t h a t

d¡ ( x; P1 ) + d
+ ( y1; P1 ) · jP1j: ( 1 1 )



2 4 On Cyclability of Digraphs with a Manoussakis-type Condition

s in c e x1x =2 A ( D ) a n d t h e a r c xy1 c a n n o t b e in s e r t e d in t o P1 ( fo r o t h e r wis e , D c o n t a in s a
c yc le wh ic h c o n t a in s a ll Y -ve r t ic e s o f C a n d Y -ve r t ic e s x; y, wh ic h is a c o n t r a d ic t io n ) . Fr o m
t h e m in im a lit y o f t h e g a p a, t h e e xis t e n c e o f t h e p a t h s P2; P3 ( b y Cla im 1 ) a n d Cla im 2 it
fo llo ws t h a t

d+ ( y1; P [ H ) = d¡ ( x; C[x2; xa]) = d¡ ( x; P ) = 0 : ( 1 2 )
Cle a r ly,

d+ ( y1; S ) · jSj ¡ 1 a n d d¡ ( x; H0 ) · jH0j; ( 1 3 )
wh e r e S := C[x2; xa] ¡ P1. B y a d d in g t h e a b o ve r e la t io n s ( 1 0 ) -( 1 3 ) , we o b t a in

d+ ( y1 ) + d
¡ ( x) = d+ ( y1; R0 ) + d

¡ ( x; R0 ) + d
¡ ( x; P1 ) + d

+ ( y1; P1 ) + d
+ ( y1; S ) + d

+ ( y1; P [ H )

+d¡ ( x; S ) + d¡ ( x; H0 ) + d¡ ( x; P ) · jR0j + jP1j + jSj + jH0j ¡ 1 · n ¡ 2 :
Th is t o g e t h e r wit h ( 9 ) g ive

d( y ) + d( y1 ) + d
¡ ( x ) + d+ ( y1 ) · 3 n ¡ 4 ;

wh ic h c o n t r a d ic t s c o n d it io n A0, s in c e y; y1 a n d x a r e Y -ve r t ic e s , y; y1 a r e n o n a d ja c e n t a n d
y1x =2 A ( D ) .

Subcase 1.2. The vertices x and y1 are nonadjacent.
W e will d is t in g u is h t wo s u b c a s e s , a c c o r d in g a s t h e r e e xis t s a ( y; x ) -p a t h in hB n ( P n fyg ) i
o r n o t .

Subcase 1.2.1. In hB n ( P n fyg ) i there is no ( y; x ) -path, in particular yx =2 A( D ) .
Th e n , c le a r ly

d+ ( y; R0 [ H0 ) + d¡ ( x; R0 [ H0 ) · jR0 [ H0j = jR0j + jH0j: ( 1 4 )

It is n o t d i± c u lt t o s e e t h a t t h e p a t h H c a n n o t b e in s e r t e d in t o C. H e n c e , fr o m L e m m a
1 it fo llo ws t h a t

d¡ ( x; C ) + d+ ( y; C ) · jCj: ( 1 5 )
Mo r e o ve r ,

d¡ ( x; P ) = d¡ ( x; E ) + d¡ ( x; L ) · jLj; s in c e d¡ ( x; E ) = 0 ;
r e c a ll t h a t E := P [z1; zk] a n d L := P [zk+1; zt], a n d b y t h e m in im a lit y o f P , we h a ve

d+ ( y; P ) = d+ ( y; E ) + d+ ( y; L) · jEj + 1 ; s in c e d+ ( y; L) · 1 :

H e n c e ,
d¡ ( x; P ) + d+ ( y; P ) · jLj + jEj + 1 = jP j:

Th e la s t in e qu a lit y t o g e t h e r wit h ( 1 4 ) , ( 1 5 ) a n d ( 9 ) im p ly t h a t

d( y ) + d( y1 ) + d
¡ ( x ) + d+ ( y ) · 2 n ¡ 2 + jRj + jH0j + jCj + jP j = 3 n ¡ 3 ;

wh ic h c o n t r a d ic t s c o n d it io n A0, s in c e y; y1 a n d x a r e Y -ve r t ic e s , y; y1 a r e n o n a d ja c e n t a n d
yx =2 A ( D ) .

Subcase 1.2.2. In hB n ( P n fyg ) i there is a ( y; x) -path.
Fir s t c o n s id e r t h e c a s e wh e n in hB n ( P [ H n fx; yg ) i t h e r e is a ( y; x ) -p a t h . L e t Q b e a

s h o r t e s t ( y; x ) -p a t h in hB n ( P [ H n fx; yg ) i.



S. Darbinyan 2 5

L e t R1 := B n ( P [ H [ Q) . W e wa n t t o c o m p u t e t h e d e g r e e s u m o f t h e ve r t ic e s x a n d
y1. Fr o m t h e m in im a lit y o f t h e C[x2; xa] a n d t h e e xis t e n c e o f t h e p a t h s H a n d Q it fo llo ws
t h a t

d ( x; R1 ) + d( y1; R1 ) · 2 jR1j a n d d( y1; H0 [ Q0 ) = 0 ; ( 1 6 )
wh e r e Q0 := Q[y+Q; x

¡
Q] ( h e r e if y

+
Q = x, t h e n Q

0 = ; ) . B y Cla im 2 , d( y1; P ) = 0 . Th is a n d
( 6 ) im p ly t h a t

d ( y1; C [ P ) · m + a ¡ 2 : ( 1 7 )
N o w we c o n s id e r t h e ve r t e x x. It is n o t d i± c u lt t o s e e t h a t x c a n n o t b e in s e r t e d in t o P

( fo r o t h e r wis e t h e r e e xis t s a ( z1; zt ) -p a t h wit h ve r t e x s e t V ( P ) [fxg wh ic h t o g e t h e r wit h t h e
a r c s x1z1; ztxa+1 a n d t h e p a t h P1 ( Cla im 1 ) fo r m s a c yc le wh ic h c o n t a in s a ll t h e Y -ve r t ic e s
o f C e xc e p t y1 b u t c o n t a in s Y -ve r t ic e s x a n d y, t h is 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 C h a s
t h e m a xim u m Y -le n g t h ) . Th e r e fo r e , b y L e m m a 2 ,

d( x; P ) · jP j + 1 : ( 1 8 )

Fr o m t h e m in im a lit y o f t h e p a t h s H a n d Q it fo llo ws t h a t

d( x; Q0 ) · jQ0j + 1 a n d d( x; H0 ) · jH0j + 1 : ( 1 9 )

S in c e t h e g a p a is m in im a l, we o b t a in t h a t d ( x; C[x2; xa]) = 0 . U s in g t h e p a t h P1 ( Cla im
1 ) , it is n o t d i± c u lt t o s e e t h a t x1x =2 A ( D ) a n d xxa+1 =2 A( D ) . Th e r e fo r e , b y L e m m a 2 ,
d( x; C ) = d( x; C[xa+1; x1]) · m ¡ a, s in c e x c a n n o t b e in s e r t e d in t o C. S u m m in g t h e a b o ve
in e qu a lit ie s ( 1 6 ) -( 1 9 ) a n d t h e la s t in e qu a lit y, a n e a s y c o m p u t a t io n s h o ws t h a t

d( y1 ) + d( x ) · 2 jR1j + 2 m + jP j + jQ0j + jH0j + 1 · 2 n ¡ 2 :

Th is t o g e t h e r wit h d( y1 ) + d( y ) · 2 n ¡ 2 ( b y ( 9 ) ) c o n t r a d ic t L e m m a 7 , s in c e y1; x a n d y1; y
a r e t wo d is t in c t p a ir s o f n o n a d ja c e n t ve r t ic e s in Y .

N o w c o n s id e r t h e c a s e wh e n a n y ( y; x ) -p a t h in hB n ( P n fyg) i h a s a c o m m o n in t e r n a l
ve r t e x wit h ( x; y ) -p a t h H. Th e n , in p a r t ic u la r , t h e ve r t ic e s y a n d x a r e n o n a d ja c e n t . L e t T
b e a s h o r t e s t ( y; x ) -p a t h in hB n ( P n fyg ) i.

D e n o t e T 0 := T [y+T ; x
¡
T ] a n d R2 := B n ( P [ H0 [ T 0 [ fxg ) . Ob s e r ve t h a t jH0j ¸ 1 a n d

jT 0j ¸ 1 s in c e y a n d x a r e n o n a d ja c e n t .
N o w we wa n t t o c o m p u t e t h e s u m d+ ( x ) + d¡ ( y ) . It is e a s y t o s e e t h a t

d+ ( x; R2 ) + d
¡ ( y; R2 ) · jR2j; ( 2 0 )

s in c e fo r o t h e r wis e in hB n ( P nfyg ) i t h e r e e xis t s a m in im a l ( y; x ) -p a t h wh ic h h a s n o c o m m o n
in t e r n a l ve r t e x wit h t h e T . Ob s e r ve t h a t ( y; x ) -p a t h T c a n n o t b e in s e r t e d in t o C[xa+1; x1] ( fo r
o t h e r wis e in D t h e r e is a c yc le wh ic h c o n t a in s m o r e Y -ve r t ic e s t h a n t h e c yc le C ) . N o t ic e t h a t
xxa+1 =2 A( D ) ( fo r o t h e r wis e , if xxa+1 2 A ( D ) , t h e n t h e p a t h s P [z1; y], T a n d P1 ( Cla im 1 )
a n d t h e a r c s xxa+1, x1z1 fo r m a c yc le wh ic h h a s m o r e Y -le n g t h t h a n t h e c yc le C ) . Th e r e fo r e ,
b y L e m m a 2 we h a ve

d+ ( x; C[xa+1; x1]) +d
¡ ( y; C[xa+1; x1]) · m¡a+d¡ ( y; fx1g ) +d+ ( x; fxa+1g ) · m¡a+1 : ( 2 1 )

Fr o m t h e m in im a lit y o f C[x2; xa] ( i.e ., o f t h e g a p a) a n d t h e e xis t e n c e o f t h e p a t h T it fo llo ws
t h a t

d¡ ( y; C[x2; xa]) = d
+ ( x; C[x2; xa]) = 0 : ( 2 2 )



2 6 On Cyclability of Digraphs with a Manoussakis-type Condition

B y t h e m in im a lit y o f P we h a ve

d¡ ( y; P ) = d¡ ( y; E ) + d¡ ( y; L) · jLj + 1 :
It is n o t d i± c u lt t o s e e t h a t

d+ ( x; P ) = d+ ( x; E ) + d+ ( x; L ) · jEj;
s in c e if xzj 2 A( D ) fo r s o m e j 2 [k + 1 ; t], t h e n u s in g t h e p a t h s T , P1 a n d t h e s u b p a t h s
P [z1; y], P [zj ; zt] we c a n o b t a in a c yc le wh ic h c o n t a in s m o r e Y -ve r t ic e s t h a n C. Th e la s t t wo
in e qu a lit ie s im p ly t h a t

d¡ ( y; P ) + d+ ( x; P ) · jLj + jEj + 1 = jP j: ( 2 3 )
It r e m a in s t o c o m p u t e d+ ( x; H0 [ T 0 ) a n d d¡ ( y; H0 [ T 0 ) . D e n o t e T 00 := T 0 n H0. Fr o m

t h e m in im a lit y o f t h e p a t h H it fo llo ws t h a t d+ ( x; H0 ) = d¡ ( y; H0 ) = 1 .
Th is t o g e t h e r wit h t h e a b o ve e xp r e s s io n s ( 2 0 ) -( 2 3 ) im p ly t h a t

d+ ( x) +d¡ ( y ) = d+ ( x; R2 ) +d
¡ ( y; R2 ) +d

+ ( x; C[xa+1; x1]) +d
¡ ( y; C[xa+1; x1]) +d

+ ( x; C[x2; xa])

+d¡ ( y; C[x2; xa]) + d
+ ( x; P ) + d¡ ( y; P ) + d+ ( x; H0 ) + d¡ ( y; H0 ) + d+ ( x; T 00 ) + d¡ ( y; T 00 )

· jR2j + m ¡ a + 1 + jP j + 2 + d+ ( x; T 00 ) + d¡ ( y; T 00 )
= jR2j + jCj + jP j + 3 + d+ ( x; T 00 ) + d¡ ( y; T 00 ) ¡ a: ( 2 4 )

A s s u m e t h a t jH0j ¸ 2 , t h e n d+ ( x; T 00 ) +d¡ ( y; T 00 ) · jT 00j, s in c e o t h e r wis e in hBn ( P nfyg ) i
t h e r e is a n ( x; y ) -p a t h s h o r t e r t h a n H. Th e la s t in e qu a lit y t o g e t h e r wit h ( 2 4 ) g ive

d+ ( x ) + d¡ ( y ) · jR2j + jCj + jP j + 3 + jT 00j ¡ a + jH0j ¡ jH0j
= n + 2 ¡ a ¡ jH0j · n ¡ 2 ;

s in c e a ¸ 2 a n d jH0j ¸ 2 . Th is t o g e t h e r wit h ( 9 ) im p ly t h a t
d( y ) + d ( y1 ) + d

¡ ( y ) + d+ ( x) · 3 n ¡ 4 ; ( 2 5 )
wh ic h c o n t r a d ic t s c o n d it io n A0 s in c e x; y; y1 a r e Y -ve r t ic e s , y; y1 a r e n o n a d ja c e n t a n d xy =2
A( D ) .

N o w a s s u m e t h a t jH0j = 1 . W e m a y a s s u m e t h a t jT 0j = 1 ( fo r o t h e r wis e , we c o n s id e r t h e
c o n ve r s e d ig r a p h o f D ) . It fo llo ws t h a t T 00 = ;. N o w u s in g ( 9 ) , ( 2 4 ) , a ¸ 2 a n d jH0j ¸ 1 , we
s e e t h a t a g a in ( 2 5 ) is t r u e , wh ic h is a c o n t r a d ic t io n . Th e d is c u s s io n o f Ca s e 1 is c o m p le t e d .

Case 2: In hB n ( P n fyg ) i there is no path between the vertices x and y. In particular,
x and y are nonadjacent.

L e t R3 := B n ( P [ fxg ) . Th e n it is e a s y t o s e e t h a t
d( x; R3 ) + d( y; R3 ) · 2 jRj;

s in c e in hB n ( P n fyg ) i t h e r e is n o p a t h b e t we e n x a n d y. U s in g L e m m a s 1 a n d 2 we o b t a in
t h a t

d ( x; P ) · jP j + 1 a n d d ( x; C ) · m;
s in c e t h e ve r t e x x c a n b e in s e r t e d n e it h e r in t o P n o r in C. Th e la s t t h r e e in e qu a lit ie s t o g e t h e r
wit h ( 4 ) a n d ( 5 ) im p ly t h a t

d( y ) + d( x ) · 2 jR3j + jP j + m + m ¡ a + jP j + 2 · 2 n ¡ a · 2 n ¡ 2 :
Th is t o g e t h e r wit h ( 9 ) c o n t r a d ic t L e m m a 7 , s in c e fx; yg a n d fy; y1g a r e t wo d is t in c t p a ir s
o f n o n a d ja c e n t ve r t ic e s o f Y . Th e d is c u s s io n o f Ca s e 2 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 .



S. Darbinyan 2 7

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

Ob s e r ve t h a t t h e e xa m p le o f t h e d ig r a p h in R e m a r k 1 is n o t 2 -s t r o n g ly c o n n e c t e d a n d jY j = 3 .
W e b e lie ve t h a t t h e fo llo win g m a y b e t r u e .
Conjectur e 1: L et D be a digraph of order n ¸ 4 and let Y be a nonempty subset of
vertices of D which satis¯es condition A0. Then D has a cycle that contains all the vertices
of Y if either (i) or (ii) or (iii) below is satis¯ed:

(i) D is 2-strongly connected.
(ii) D is Y -strongly connected and jY j ¸ 4 .
(iii) for any ordered pair of distinct vertices x; y of Y there are two internally disjoint

paths from x to y in D.
C. Th o m a s s e n [1 8 ] ( fo r n = 2 k + 1 ) a n d t h e a u t h o r [1 9 ] ( fo r n = 2 k ) p r o ve d t h e fo llo win g

t h e o r e m .
T heor em H : ( C.Th o m a s s e n [1 8 ], S . D a r b in ya n [1 9 ]) . L et D be a digraph of order n ¸ 5
with minimum degree at least n ¡ 1 and with minimum semi-degree at least n=2 ¡ 1 . Then D
is Hamiltonian or belongs to a non-empty ¯nite family of non-Hamiltonian digraphs, which
are characterized.

A qu e s t io n wa s p u t in [2 0 ]:
L e t D b e a d ig r a p h o f o r d e r n ¸ 5 a n d le t T 6= ; b e a s u b s e t o f V ( D ) . A s s u m e t h a t D

is s t r o n g ly c o n n e c t e d ( o r D is T -s t r o n g ly c o n n e c t e d ) a n d e ve r y ve r t e x o f T h a s a d e g r e e a t
le a s t n ¡ 1 a n d h a s a n o u t d e g r e e a n d a n in d e g r e e a t le a s t n=2 ¡ 1 . D o e s D h a ve a c yc le t h a t
c o n t a in s a ll t h e ve r t ic e s o f T ?.

Fo r n = 2 m + 1 in [2 0 ] it wa s p r o ve d :
If D is strongly connected and contains a cycle of length n ¡ 1 , then D has a cycle

containing all the vertices of T unless some extremal cases.

A c kn o wle d g m e n t s

W e wo u ld like t o t h a n k t h e r e fe r e e s fo r m a n y u s e fu l s u g g e s t io n s , wh ic h h a ve c o n s id e r a b ly
im p r o ve d t h e p r e s e n t a t io n o f t h e p a p e r .

Refer ences

[1 ] B . B o llo b a s , G. B r ig h t we ll, \ Cyc le s t h r o u g h s p e c ī e d ve r t ic e s " , Combinatorica, vo l. 1 3 ,
n o . 2 , p p . 1 1 7 -1 5 5 , 1 9 9 3 .

[2 ] K . Ot a , \ Cyc le s t h r o u g h p r e s c r ib e d ve r t ic e s wit h la r g e d e g r e e s u m " , D iscrete M athe-
matics, vo l. 1 4 , p p . 2 0 1 -2 1 0 , 1 9 9 5 .

[3 ] R . S h i,\ 2 -N e ig h b o u r h o o d a n d h a m ilt o n ia n c o n d it io n s " , J ournal of Graph Theory 16,
p p . 2 6 7 -2 7 1 , 1 9 9 2 .

[4 ] H . J. V e ld m a n , " Cyc le s c o n t a in in g m a n y ve r t ic e s o f la r g e d e g r e e " , D iscrete M athematics,
vo l. 1 0 1 , p p . 3 1 9 -3 2 5 , 1 9 9 2 .

[5 ] H . L i, E . Fla n d r in a n d J. S h u , \ A s u ± c ie n t c o n d it io n fo r c yc la b ilit y in d ir e c t e d g r a p h s " ,
D iscrete M athematics, vo l. 3 0 7 , p p . 1 2 9 1 -1 2 9 7 , 2 0 0 7 .

[6 ] 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 of Combinatorial Theory B , vo l. 1 4 , p p . 1 3 7 -1 4 7 , 1 9 7 3 .



2 8 On Cyclability of Digraphs with a Manoussakis-type Condition

[7 ] 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 " , C.
R . Acad. Sci. P aris A-b, vo l. 2 5 1 , p p . 4 9 5 -4 9 7 , 1 9 6 0 .

[8 ] 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 rocceding L ondon M athe-
matical Society, vo l. 2 4 , p p . 7 3 9 -7 5 5 , 1 9 7 2 .

[9 ] J. A . B o n d y a n d 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 ath-
ematics, vo l. 1 9 , p p . 1 9 5 -1 9 7 , 1 9 7 7 .

[1 0 ] D . B . W e s t , Introduction to Graph Theory, P r e t ic e -H a ll, N e w D e lh i, 2 0 0 1 .

[1 1 ] 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
la r g e s e m id e g r e e s " , Akademy Nauk Armyan. SSR D okl., vo l. 8 2 , n o . 1 , p p . 6 -8 , 1 9 8 6
( 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 ) .

[1 2 ] K . A . B e r m a n a n d X . L iu , \ Cyc le s t h r o u g h la r g e d e g r e e ve r t ic e s in d ig r a p h s : A g e n -
e r a liz a t io n o f Me yn ie l's t h e o r e m " , it Jo u r n a l o f Co m b in a t o r ia l Th e o r y B , vo l. 7 4 , p p .
2 0 -2 7 , 1 9 9 8 .

[1 3 ] Y . Ma n o u s s a kis , \ D ir e c t e d H a m ilt o n ia n g r a p h s " , J ournal of Graph Theory, vo l. 1 6 , n o .
1 , p p . 5 1 -5 9 , 1 9 9 2 .

[1 4 ] J. B a n g -Je n s e n , G. Gu t in a n d 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 il-
t 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 .

[1 5 ] J. B a n g -Je n s e n , Y . Gu o a n d 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 ilt o n ia n " , D iscrete Applied M athematics, vo l. 9 5 , p p . 7 7 -8 7 , 1 9 9 9 .

[1 6 ] J. B a n g -Je n s e n a n d 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 , L o n d o n , 2 0 0 1 .

[1 7 ] R . H Äa g g kvis t a n d 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 of Combinatorial
Theory B , vo l. 2 0 , p p . 2 0 -4 0 , 1 9 7 6 .

[1 8 ] 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 rocceding 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 9 ] 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
la r g e s e m id e g r e e s " , Akademy Nauk Armyan. SSR D okl., vo l. 8 2 , n o . 1 , p p . 6 -8 , 1 9 8 6
( 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 ) .

[2 0 ] S . K h . D a r b in ya n a n d I.A . K a r a p e t ya n , \ On c yc le s t h r o u g h ve r t ic e s o f la r g e s e m id e g r e e
in d ig r a p h s " , M athematical P roblems of Computer Science, vo l. 3 9 , p p .1 0 6 -1 1 8 , 2 0 1 3 .

Submitted 02.11.2016, accepted 26.01.2017

سÝááõë³ÏÇëÇ ïÇåÇ å³ÛÙ³ÝÇÝ µ³í³ñ³ñáÕ ÏáÕÙÝáñáßí³Í
·ñ³ýÝ»ñÇ óÇÏÉÇÏáõÃÛ³Ý Ù³ëÇÝ

ê. ¸³ñµÇÝÛ³Ý

²Ù÷á÷áõÙ

Ü»ñϳ ³ß˳ï³ÝùáõÙ óáõÛó ¿ ïñíáõÙ áñ »Ã» ÏáÕÙÝáñáßí³Í ·ñ³ýÇ ·³·³ÃÝ»ñÇ Y
»Ýóµ³½ÙáõÃÛáõÝÁ µ³í³ñ³ñáõÙ ¿ D ÏáÕÙÝáñáßí³Í ·ñ³ýÝ»ñÇ Ñ³Ù³ñ سÝááõë³ÏÇëÇ



S. Darbinyan 2 9

ѳÙÇÉïáÝÛ³ÝáõÃÛ³Ý µ³í³ñ³ñ å³ÛÙ³ÝÇÝ (J. Graph Theory, 16, 1992), ³å³ ³Û¹ ·ñ³ýÁ
å³ñáõݳÏáõÙ ¿ óÇÏÉ, áñÝ ³ÝóÝáõÙ ¿ Y »Ýóµ³½ÙáõÃÛ³ÝÁ å³ïϳÝáÕ µáÉáñ ·³·³ÃÝ»ñáí
µ³óÇ ·áõó» Ù»ÏÇó: êï³óí³Í ³ñ¹ÛáõÝùÁ ÉáõÍáõÙ ¿ ÈÇÇ, üɳݹñÇÝÇ ¨ ÞáõÇ (Discrete Math-
ematics, 307, 2007) ÏáÕÙÇó ³é³ç³ñÏ³Í ËݹÇñÁ:

Î öèêëè÷íîñòè îðãðàôîâ ïðè óñëîâèé òèïà Ìàíîóñàêèñà
Ñ. Äàðáèíÿí

Àííîòàöèÿ

 ðàáîòå äîêàçàíî, ÷òî åñëè ïîäìíîæåñòâî Y âåðøèí îðãðàôà D
óäîâëåòâîðÿåò äîñòàòî÷íîìó óñëîâèþ ãàìèëüòîíîâñòè Ìàíîóñàêèñà (J. Graph
Theory, 16, 1992 ), òî â D ñóùåñòâóåò êîíòóð, êîòîðûé ñîäåðæèò ïî êðàéíåé
ìåðå jY j¡ 1 âåðøèí ïîäìíîæåñòâà Y . Ïîëó÷åííûé ðåçóëüòàò ðåøàåò çàäà÷ó Ëè,
Ôëàíäðèí è Øó (Discrete Mathematics, 307, 2007).