14_Samve_Darbinyan.DVI


Mathematical Problems of Computer Science 39, 106{118, 2013.

On Cycles T hr ough Ver tices of Lar ge Semidegr ee in

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 strong digraph on n = 2m + 1 ¸ 5 vertices. In this paper we show that
if D contains a cycle of length n¡1, then D has also a cycle which contains all vertices
with in-degree and out-degree at least m (unless some extremal cases).

Keywords: digraphs, cycles, Hamiltonian cycles, cyclability.

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

Th e 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 o f le n g t h jV ( D ) j.
A s e t S o f ve r t ic e s in a d ig 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 ( G ) c o n t a in s a c yc le t h r o u g h a ll 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 [4 , 5 , 1 5 , 1 6 , 1 8 ]) . H o we ve r , fo r g e n e r a l d ig r a p h s , r e la t ive ly
fe w d e g r e e c o n d it io n s a r e kn o wn t o g u a r a n t e e h a m ilt o n is it y in d ig r a p h s ( S e e [2 , 3 , 7 , 9 , 1 3 ,
1 4 , 1 7 , 1 9 ]) . 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 is t h e fo llo win g t h e o r e m o f M. Me yn ie l:

T heor em A [1 3 ]. If D is a strong digraph of order n ¸ 2 and d( x ) + d( y ) ¸ 2 n ¡ 1 for
all pairs of nonadjacent vertices in D, then D is hamiltonian .

In [8 ], 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 heor em B [8 ]. L et D be a strong digraph of order n ¸ 3 . If d( x ) + d( y ) ¸ 2 n ¡ 1 for

any two non-adjacent vertices x; y 2 V ( D ) ¡ fz0g, where z0 is some vertex of D, then D is
hamiltonian or contains a cycle of length n ¡ 1 .
The following result is immediately corollary of Theorem B .

Cor ollar y [8 ]. L et D be a strong 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 .

A Me yn ie l s e t M is a s u b s e t o f V ( 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
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. In [4 ], K . A . B e r m a n a n d X . L iu im p r o ve d
Th e o r e m B 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 Me yn ie l's t h e o r e m .

T heor em C [4 ]. L et D be a digraph of order n. If D is strongly connected, then every
M eyniel set M lies in a cycle.
Th e o r e m C a ls o g e n e r a liz e s t h e c la s s ic a l t h e o r e m s A . Gh o u ila -H o u r i [1 1 ] a n d D .R . W o o d a ll
[1 9 ].

1 0 6



S. Darbinyan and I. Karapetyan 1 0 7

Th e 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 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 in D ( S e e [1 2 ]) . H . L i, E . Fla n d r in a n d J.
S h u [1 2 ] 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 C.

T heor em D [1 2 ]. 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 vertices of M.

C. Th o m a s s e n [1 7 ] ( fo r n = 2 k + 1 ) a n d t h e ¯ r s t a u t h o r [7 ] ( fo r n = 2 k ) p r o ve d t h e
fo llo win g :

T heor em E [1 7 , 7 ]. If D is 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 (unless some
extremal cases which are characterized).

W e p u t a qu e s t io n t o kn o w if t h is r e s u lt o f C. Th o m a s s e n a n d t h e ¯ r s t a u t h o r h a s a
c yc la b le ve r s io n .

L e t D b e a d ig r a p h o f o r d e r n = 2 m + 1 . A Th o m a s s e n s e t T is a s u b s e t o f V ( D ) s u c h
t h a t d+ ( x ) ¸ m a n d d¡ ( x ) ¸ m fo r e ve r y x 2 T , we d e n o t e t h e ve r t ic e s o f T b y T -ve r t ic e s .
Th e c yc le c o n t a in in g a ll ve r t ic e s o f T is c a lle d a T -c yc le .

In t h is p a p e r we p r o ve t h e fo llo win g t wo t h e o r e m s wh ic h p r o vid e s o m e s u p p o r t fo r t h e
a b o ve qu e s t io n .

T heor em 1. L et D be a strong digraph of order n = 2 m + 1 ¸ 3 and D contains a cycle
of length n ¡ 1 . Then one of the following holds:

i. D contains a cycle containing all vertices with in-degree and out-degree at least m;
ii. D is isomorphic to digraphs D5 or D7 or belongs to the set L1 [ L2;
iii. K¤m;m+1 µ D µ [Km + Km+1]¤;
iv. D contains a cycle C := x1x2 : : : x2mx1 of length n ¡ 1 , and if x =2 V ( C ) and x is not

adjacent to the vertices xl1; xl2 ; : : : ; xlj , j ¸ 3 , then xli¡1x; xxli+1 2 D and N + ( x ) = N + ( xli )
and N ¡ ( x ) = N¡ ( xli ) for all i 2 [1 ; j]. In particular, fxl1; xl2; : : : ; xlj ; xg is an independent
set of vertices.

T heor em 2. L et D be a 2-strong digraph of order n = 2 m + 1 ¸ 3 . Then any two
T -vertices x and y are on a common cycle in D.

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 o f [1 7 , 7 ].

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 m o n o g r a p h o f B a n g -Je n s e n a n d Gu t in [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 jDj 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. 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 jo in 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 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 hAi. 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 x1x2 ¢ ¢ ¢ xm ( r e s p e c t ive ly, x1x2 ¢ ¢ ¢ xmx1 ) . Fo r a
c yc le Ck = x1x2 ¢ ¢ ¢ xkx1, 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]



1 0 8 On Cycles Through Vertices of Large Semidegree in Digraphs

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¤ 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 . Kn
( r e s p e c t ive ly, Kp;q ) d e n o t e s t h e c o m p le t e g r a p h o f o r d e r n ( r e s p e c t ive ly, 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 ) , a n d Kn d e n o t e s t h e c o m p le m e n t o f c o m p le t e
u n d ir e c t e d g r a p h o f o r d e r n. 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 ) . W e d e n o t e b y a ( x; y ) t h e n u m b e r o f a r c s b e t we e n t h e ve r t ic e s x a n d
y. In p a r t ic u la r , a( x; y ) = 0 ( r e s p e c t ive ly, a( x; y ) 6= 0 ) m e a n s t h a t x a n d y a r e n o t a d ja c e n t
( r e s p e c t ive ly, a r e a d ja c e n t ) . 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

Th e fo llo win g we ll-kn o wn s im p le le m m a s 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 p r o o fs o f o u r
r e s u lt s .

Lemma 1 [1 0 ]. L et D be a digraph on n ¸ 3 vertices 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 ].

Lemma 2 [6 ]. L et D be a digraph on n ¸ 3 vertices 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, 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 ).

4 . P r o o f o f Th e o r e m 1

H e r e we p r o ve o n ly Th e o r e m 1 a n d fo r it we n e e d t h e fo llo win g d e ¯ n it io n s .
De¯nition 1. D7 is a digraph (see [1, 17]) with the vertex set V ( D7 ) =

fx1; x2; x3; x4; x5; x; yg such that N + ( x1 ) = fx2; x5; yg, N + ( x2 ) = fx3; x4; yg, N + ( x3 ) =
fx2; x4; xg, N + ( x4 ) = fx3; x5; xg, N + ( x5 ) = fx1; x; yg, N + ( x ) = fx1; x2; x3g and N + ( y ) =
fx1; x4; x5g.

De¯nition 2. D5 is a digraph (see [1, 17]) with the vertex set V ( D5 ) = fx1; x2; x3; x; yg
such that N + ( x1 ) = fx2; yg, N + ( x2 ) = fx3; xg, N + ( x3 ) = fx; yg, N + ( x ) = fx1; x2g and
N + ( y ) = fx1; x3g.

W e d e n o t e b y L1 t h e s e t o f t h r e e d ig r a p h s o b t a in e d fr o m D5 b y a d d in g t h e a r c x1x3 o r
x3x1 ( o r b o t h ) .

De¯nition 3. B y L2 we denote the set of digraphs D with the vertex set V ( D ) =
fx1; x2; : : : ; x2m; xg and with the following properties:

i. D contains a cycle x1x2 : : : x2mx1 of length 2 m and the vertices x and x2m are not
adjacent;

ii. N + ( x ) =N + ( x2m ) =fx1; x2; : : : ; xmg and N¡ ( x) =N ¡ ( x2m ) = fxm; xm+1; : : : ; x2m¡1g;



S. Darbinyan and I. Karapetyan 1 0 9

iii. A ( fx1; x2; : : : ; xm¡1g ! fxm+1; xm+2; : : : ; x2m¡1g ) = ;, the induced subdigraphs
hfx1; x2; : : : ; xmgi and hfxm; xm+1; : : : ; x2m¡1gi are arbitrary and one may add any number
of arcs that go from fxm+1; xm+2; : : : ; x2m¡1g to fx1; x2; : : : ; xmg. (Note that the digraphs
from L2 are not 2-strong and x, x2m are T -vertices which are not in the common cycle.

P r oof of T heor em 1. Th e p r o o f is b y c o n t r a d ic t io n . S u p p o s e t h a t Th e o r e m 2 is fa ls e ,
in p a r t ic u la r , D is n o t h a m ilt o n ia n . 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 t h e ve r t e x x is n o t c o n t a in in g t h is c yc le C. In fu r t h e r , b y H we d e n o t e a
h a m ilt o n ia n c yc le in D.

Th e n x is a T -ve r t e x. S in c e C is a lo n g e s t c yc le , u s in g L e m m a s 1 a n d 2 , we o b t a in t h e
fo llo win g c la im :

Claim 1. ( i) . d( x ) = n ¡ 1 a n d t h e r e is a ve r t e x xl, l 2 [1 ; n ¡ 1 ] wh ic h is n o t a d ja c e n t
t o x.

( ii) . If xix =2 D, t h e n xxi+1 2 D a n d if xxi =2 D, t h e n xi¡1x 2 D, wh e r e i 2 [1 ; n ¡ 1 ].
( iii) . If t h e ve r t ic e s x a n d xi a r e n o t a d ja c e n t , t h e n xi¡1x; xxi+1 2 D a n d d ( xi ) = n ¡ 1 .

B y Cla im 1 ( 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 t h e ve r t ic e s x a n d xn¡1
a r e n o t a d ja c e n t . Fo r c o n ve n ie n c e , le t p := n ¡ 2 a n d y := xn¡1. W e h a ve yx1; xpy 2 D a n d
xpx, xx1 2 D b y Cla im 1 ( iii) . Th e r e fo r e , y is a T -ve r t e x a n d d( y ) = n ¡ 1 .

Claim 2. A t le a s t t wo ve r t ic e s o f C a r e n o t a d ja c e n t t o x u n le s s D is is o m o r p h ic t o D5
o r D7 o r b e lo n g s t o t h e s e t L1 [ L2.

P r oof. W e p r o ve Cla im 2 b y c o n t r a d ic t io n . L e t C := x1x2 : : : xn¡1x1. Th e n , b y L e m m a
1 , d ( x ) = n ¡ 1 a n d d+ ( x ) = d¡ ( x ) = m, s in c e D is n o t h a m ilt o n ia n . It is e a s y t o s e e t h a t
s o m e ve r t e x xi ( s a y, y := xn¡1 ) is n o t a d ja c e n t t o x. Th e n , b y Cla im 1 ( iii) , xpx, xx1 2 D.
If y is n o t a T -ve r t e x, t h e n t h e c yc le x1x2 : : : xn¡2yx1 c o n t a in s a ll T -ve r t ic e s . S o , we c a n
a s s u m e t h a t y is a T -ve r t e x. Th e n d( y ) = n ¡ 1 ( b y L e m m a 1 ) a n d d+ ( y ) = d¡ ( y ) = m.
Fr o m o u r a s s u m p t io n it fo llo ws t h a t

N + ( x ) = fx1; x2; : : : ; xmg a n d N ¡ ( x ) = fxm; xm+1; : : : ; xpg: ( 1 )

W e ¯ r s t p r o ve t h a t t h e r e is a ve r t e x xk, k 2 [2 ; p ¡ 1 ], wh ic h is n o t a d ja c e n t t o y. A s s u m e
t h a t it is n o t t h e c a s e . Th e n

N + ( y ) = fx1; x2; : : : ; xmg a n d N ¡ ( y ) = fxm; xm+1; : : : ; xpg: ( 2 )

S in c e D is n o t h a m ilt o n ia n we h a ve

A( fx1; : : : ; xm¡1g ! fxm+1; : : : ; xpg ) = ;; ( 3 )

fo r o t h e r wis e , if xixj 2 D, wh e r e i 2 [1 ; m ¡ 1 ] a n d j 2 [m + 1 ; n ¡ 2 ], t h e n b y ( 1 ) a n d ( 2 ) ,
H = x1 : : : xixj : : : xpxxi+1 : : : xj¡1yx1 is a h a m ilt o n ia n c yc le . Th e r e fo r e

A ( fx1; : : : ; xm¡1; x; yg ! fxm+1; : : : ; xn¡2g ) = ;;
i.e ., D b e lo n g s t o t h e s e t L2 wh ic h is a c o n t r a d ic t io n .

Th u s , t h e r e is a ve r t e x xk wit h k 2 [2 ; p ¡ 1 ] wh ic h is n o t a d ja c e n t t o y. B y Cla im 1 ( iii) ,
xk¡1y; yxk+1 2 D. Ob s e r ve t h a t xk a ls o is a T -ve r t e x. If k 2 [m + 1 ; p ¡ 1 ], t h e n m ¸ 3 a n d
fr o m d¡ ( xk; fx; yg) = 0 it fo llo ws t h a t t h e r e is a ve r t e x xi, i 2 [1 ; m¡ 1 ], s u c h t h a t xixk 2 D.
Th e r e fo r e H = x1 : : : xixk : : : xpxxi+1 : : : xk¡1yx1, a c o n t r a d ic t io n . S o , we c a n a s s u m e t h a t
k · m. S im ila r ly, we c a n a s s u m e t h a t k ¸ m. Th e r e fo r e it r e m a in s t o c o n s id e r t h e c a s e
wh e n m = k a n d t h e ve r t e x y is a d ja c e n t t o a ll ve r t ic e s o f P n fxmg. If n = 5 , i.e ., m = 2 ,
t h e n x1y; yx3 2 D a n d x2x1 =2 D, x3x2 =2 D, i.e ., D is is o m o r p h ic t o t h e we ll-kn o wn d ig r a p h



1 1 0 On Cycles Through Vertices of Large Semidegree in Digraphs

D5 o r D 2 L, s in c e if we a d d t h e a r c x1x3 o r x3x1 ( o r b o t h ) t o D5, t h e n t h e r e s u lt in g d ig r a p h
a ls o is n o t h a m ilt o n ia n , i.e ., D 2 L1. A s s u m e t h a t m ¸ 3 . It is n o t d i± c u lt t o s e e t h a t

d( xm; fx1; xpg ) = 0 a n d A ( fx1; : : : ; xm¡2g ! xm ) = A ( xm ! fxm+2; : : : ; xpg ) = ;; ( 4 )

in p a r t ic u la r , xm is n o t a d ja c e n t t o x1 a n d xp. Th e r e fo r e

fxm+1; : : : ; xp¡1g ! xm ! fx2; : : : ; xm¡1g: ( 5 )

Th is im p lie s t h a t xp a n d x1 a r e T -ve r t ic e s , s in c e x1 : : : xm¡1yxm+1 : : : xp¡1xmxx1 ( r e s p e c -
t ive ly, x2 : : : xm¡1y xm+1 : : : xpxxmx2 ) 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 xp
( r e s p e c t ive ly, x1 ) .

N o w we c o n s id e r t h e ve r t e x y. If xp¡1y 2 D, t h e n xxp =2 D a n d yxp =2 D im p ly t h a t
xixp 2 D fo r s o m e i 2 [1 ; m¡ 1 ], a n d h e n c e H = x1 : : : xixpxxi+1 : : : xp¡1yx1, a c o n t r a d ic t io n .
S o , we c a n a s s u m e t h a t xp¡1y =2 D a n d , s im ila r ly, yx2 =2 D, i.e ., yxp¡1; x2y 2 D. U s in g
L e m m a 2 , we o b t a in t h a t

fx1; x2; : : : ; xm¡1g ! y ! fxm+1; xm+2; : : : ; xpg: ( 6 )

It is n o t d i± c u lt t o s e e t h a t d+ ( x1; P [x3; xm+1]) = 0 , fo r o t h e r wis e , if x1xi 2 D, i 2 [3 ; m],
t h e n b y ( 1 ) a n d ( 6 ) , H = x1xi : : : xpxx2 : : : xi¡1yx1, a n d if x1xm+1 2 D, t h e n b y ( 1 ) , ( 5 ) a n d
( 6 ) , H = x1xm+1 : : : xpxxmx2 : : : xm¡1yx1, wh ic h is a c o n t r a d ic t io n . S im ila r ly, we c a n s h o w
t h a t d¡ ( xp; P [xm¡1; xp¡2]) = 0 . Th e r e fo r e

N + ( x1 ) = fx2; y; xm+2; xm+3; : : : ; xpg a n d N¡ ( xp ) = fxp¡1; y; x1; x2; : : : ; xm¡2g: ( 7 )

B y ( 7 ) , ( 5 ) a n d ( 6 ) it is e a s y t o s e e t h a t x1 : : : xm¡2xpyxm+1 : : : xp¡1xmxx1 ( r e s p e c t ive ly,
x1xm+2 : : : xpxxm x2 : : : xm¡1yx1 ) 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 xm¡1
( r e s p e c t ive ly, xm+1 ) . Th is m e a n s t h a t xm¡1 a n d xm+1 a r e T -ve r t ic e s .

N o w we will c o n s id e r t h e ve r t e x xm¡1. Th e n xm¡1xi =2 D fo r a ll i 2 [m + 2 ; p]
( fo r o t h e r wis e , b y ( 5 ) , H = x1 : : : xm¡1xi : : : xpyxm+1 : : : xi¡1xmxx1 ) a n d xm¡1x1 =2 D
( fo r o t h e r wis e , H = x1 : : : xm¡2yxm+1 : : : xpxxmxm¡1x1 b y ( 5 ) a n d ( 6 ) ) . Th u s , we h a ve
d+ ( xm¡1; fx1; x; xm+2; : : : ; xpg ) = 0 . Th e r e fo r e

xm¡1 ! fx2; : : : ; xm¡2; y; xm; xm+1g: ( 8 )

N o w, if m ¸ 4 , t h e n b y ( 7 ) , ( 1 ) , ( 8 ) a n d ( 5 ) we h a ve H = x1xpxxm¡1xm+1 : : : xp¡1xmx2 : : :
xm¡2yx1, wh ic h is a c o n t r a d ic t io n .

Th e r e fo r e m = 3 , i.e ., n = 7 . Fr o m ( 4 ) , ( 5 ) a n d ( 7 ) we o b t a in t h a t x4x3; x3x2; x1x5 2 D,
x1 a n d x5 a r e T -ve r t ic e s a n d d ( x3; fx1; x5g ) = 0 . It is e a s y t o s e e t h a t d+ ( x2; fx1; x5g ) =
d+ ( x5; fx2; x4g ) = 0 . Fr o m t h is we c o n c lu d e t h a t x5x1 2 D. N o w we s e e t h a t x1x5yx4x3xx1
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 x2. Th is m e a n s t h a t x2 is a T -ve r t e x a n d
d+ ( x2 ) = d

¡ ( x2 ) = 3 . S in c e d
+ ( x2; fx; x1; x5g ) = 0 , it fo llo ws t h a t x2x4 2 D. Th e r e fo r e D is

is o m o r p h ic t o t h e d ig r a p h D7. Cla im 2 is p r o ve d .
Claim 3. L e t xp¡1x; yxp 2 D a n d fo r s o m e k 2 [2 ; p ¡ 2 ] xk a n d y a r e n o t a d ja c e n t .

Th e n xk a n d xp a ls o a r e n o t a d ja c e n t .
P r oof. S in c e xk a n d y a r e n o t a d ja c e n t it fo llo ws t h a t xk¡1y; yxk+1 2 D ( b y Cla im

1 ( iii) ) . N o w if xkxp 2 D, t h e n H = x1 : : : xkxpyxk+1 : : : xp¡1xx1; a n d if xpxk 2 D, t h e n
H = x1 : : : xk¡1yxpxk : : : xp¡1xx1. In e a c h c a s e we h a ve o b t a in e d a h a m ilt o n ia n c yc le , wh ic h
is a c o n t r a d ic t io n .



S. Darbinyan and I. Karapetyan 1 1 1

Claim 4. If xp¡1x a n d yxp 2 D, t h e n d( xi; fx; yg ) ¸ 1 fo r a ll i 2 [2 ; p ¡ 2 ].
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( xi; fx; yg ) = 0 fo r s o m e i 2 [2 ; p ¡ 2 ]. Th e n b y

Cla im 1 ( iii) , xi¡1 ! fx; yg ! xi+1, a n d b y Cla im 3 t h e ve r t ic e s xi a n d xp a r e n o t a d ja c e n t .
N o w, s in c e xi is a T -ve r t e x a n d c a n n o t b e in s e r t e d in t o P [x1; xi¡1] a n d in t o P [xi+1; xp¡1],
u s in g L e m m a 2 , we o b t a in t h a t

p + 1 = d( xi ) = d( xi; P [x1; xi¡1]) + d( xi; P [xi+1; xp¡1]) · i + p ¡ i = p;
a c o n t r a d ic t io n .
Claim 5. If xp¡1x 2 D, t h e n t h e ve r t ic e s y a n d xp¡1 a r e a d ja c e n t .
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 y a n d xp¡1 a r e n o t a d ja c e n t . Th e n b y Cla im

1 ( iii) , xp¡2y; yxp 2 D. If xpxp¡1 2 D, t h e n H = x1 : : : xp¡2yxpxp¡1xx1, a c o n t r a d ic t io n . S o ,
we c a n a s s u m e t h a t xpxp¡1 =2 D. Mo r e o ve r , if xxi 2 D wit h i 2 [2 ; p ¡ 2 ], t h e n xi¡1xp¡1 =2 D
( fo r o t h e r wis e , we wo u ld h a ve a h a m ilt o n ia n c yc le H = x1 : : : xi¡1xp¡1xpxxi : : : xp¡2yx1 ) .
R e c a ll ( b y Cla im 2 ) t h a t t h e r e is a ve r t e x xl wit h l 2 [2 ; p ¡ 2 ] wh ic h is n o t a d ja c e n t t o
x. N o t e t h a t xl¡1x a n d xxl+1 2 D b y Cla im 1 ( iii) . S in c e x is a T -ve r t e x, it fo llo ws t h a t
d+ ( x; P [x2; xp¡2]) ¸ m ¡ 2 . If we c o n s id e r t h e ve r t e x xp¡1, t h e n fr o m d¡ ( xp¡1; fy; xpg ) = 0
a n d t h e a b o ve o b s e r va t io n it fo llo ws t h a t

xxp¡1 a n d xl¡1xp¡1 2 D: ( 9 )

H e n c e xpxl =2 D ( fo r o t h e r wis e , if xpxl 2 D, t h e n H = x1 : : : xl¡1xxp¡1xpxl : : : xp¡2yx1 ) .
Case 5.1. l · p ¡ 3 . Th e n it is n o t d i± c u lt t o s e e t h a t t h e ve r t ic e s xl a n d xp¡1 a r e

n o t a d ja c e n t . In d e e d , if xp¡1xl 2 D, t h e n H = x1 : : : xl¡1xp¡1xl : : : xp¡2yxpxx1 b y ( 9 ) ; a n d if
xlxp¡1 2 D, t h e n H = x1 : : : xlxp¡1xpxxl+1 : : : xp¡2yx1, wh ic h is a c o n t r a d ic t io n . Fr o m t h is ,

p + 1 = d( xl ) = d( xl; P [x1; xl¡1]) + d( xl; P [xl+1; xp¡2]) + d ( xl; fy; xpg ) : ( 1 0 )

N o w we s h o w t h a t
xlxp a n d xp¡2xl 2 D: ( 1 1 )

L e t ¯ r s t yxl 2 D. Th e n xlx1 =2 D ( fo r o t h e r wis e , H = x1 : : : xl¡1xxl+1 : : : xpyxlx1 is a
h a m ilt o n ia n c yc le , a c o n t r a d ic t io n ) . S in c e t h e ve r t e x xl c a n n o t b e in s e r t e d in t o P [x1; xl¡1]
a n d P [xl+1; xp¡2], fr o m ( 1 0 ) , xpxl =2 D a n d L e m m a 2 it fo llo ws t h a t d ( xl; P [x1; xl¡1]) = l ¡ 1 ,
d( xl; P [xl+1; xp¡2]) = p ¡ l ¡ 1 a n d xlxp; xp¡2xl 2 D.

L e t n e xt yxl =2 D. S im ila r ly a s in t h e c a s e yxl 2 D we d e d u c e t h a t d( xl; P [xl+1; xp¡2]) =
p ¡ l ¡ 1 a n d xlxp; xp¡2xl 2 D. ( 1 1 ) is p r o ve d .

N o w u s in g ( 9 ) a n d ( 1 1 ) , we o b t a in a h a m ilt o n ia n c yc le H = x1 : : : xl¡1xp¡1xxl+1 : : : xp¡2xlxpyx1,
wh ic h is a c o n t r a d ic t io n .

Case 5.2. l = p ¡ 2 . Th e n xpxp¡2 =2 D a n d d ( xp¡2; fxp¡1; xpg ) · 2 . B y t h e c o n s id e r e d
c a s e l · p ¡ 3 , w.l.o .g . we c a n a s s u m e t h a t t h e ve r t e x x is a d ja c e n t t o a ll ve r t ic e s o f
P [x1; xp¡3]. Th e n

N + ( x) = fx1; x2; : : : ; xm¡1; xp¡1g a n d N¡ ( x ) = fxm¡1; xm; : : : ; xp¡3; xp¡1; xpg: ( 1 2 )

Th is t o g e t h e r wit h fxp¡3; xp¡1; xpg ! x im p lie s t h a t m ¸ 3 a n d xx2 2 D.
Subcase 5.2.1. yx2 2 D. A s s u m e t h a t yxp¡2 =2 D. Th e n d+ ( y; P [x2; xp¡3]) = m ¡ 2

s in c e y a n d xp¡1 a r e n o t a d ja c e n t . Fr o m t h is a n d d
¡ ( xp¡2; fx; y; xpg ) = 0 it fo llo ws t h a t

xixp¡2; yxi+1 2 D fo r s o m e i 2 [1 ; p¡ 4 ]. Th e r e fo r e H = x1 : : : xixp¡2xp¡1xpyxi+1 : : : xp¡3xx1,
wh ic h is a c o n t r a d ic t io n . S o , we c a n a s s u m e t h a t yxp¡2 2 D. N o w it is e a s y t o s e e t h a t x1



1 1 2 On Cycles Through Vertices of Large Semidegree in Digraphs

a n d xp¡2 a r e n o t a d ja c e n t . In d e e d , if x1xp¡2 2 D, t h e n H = x1xp¡2xp¡1xpyx2 : : : xp¡3xx1;
a n d if xp¡2x1 2 D, t h e n H = x1 : : : xp¡3xxp¡1xpyxp¡2x1; wh ic h is a c o n t r a d ic t io n . S in c e
xp¡2 c a n n o t b e in s e r t e d in t o P [x2; xp¡3], b y L e m m a 2 we h a ve d ( xp¡2; P [x2; xp¡3]) · p ¡ 3 .
On t h e o t h e r h a n d ,

p + 1 = d( xp¡2 ) = d( xp¡2; P [x2; xp¡3]) + d ( xp¡2; fxp¡1; xpg ) + a ( xp¡2; y )
im p lie s t h a t d ( xp¡2; P [x2; xp¡3]) = p ¡ 3 . H e n c e , b y L e m m a 2 , xp¡2x2 2 D a n d

x2 : : : xp¡3xxp¡1xpyxp¡2 x2 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 x1. Th e r e -
fo r e x1 is a T -ve r t e x. N o w we c o n s id e r t h e ve r t e x x1. Ob s e r ve t h a t if x1xi 2 D,
i 2 [m; p ¡ 2 ], t h e n b y ( 1 2 ) , H = x1xi : : : xpyx2 : : : xi¡1xx1; a n d if x1xp¡1 2 D,
t h e n H = x1xp¡1xpyxp¡2x2 : : : xp¡3xx1, a c o n t r a d ic t io n . Th e r e fo r e d

+ ( x1; fx; y; xm; xm+1;
: : : ; xp¡1g ) = 0 wh ic h c o n t r a d ic t s t h a t x is a T -ve r t e x.

Subcase 5.2.2. Th e ve r t ic e s x2 a n d y a r e n o t a d ja c e n t . Th e n x1y; yx3 2 D b y Cla im
1 ( iii) , a n d b y Cla im 3 t h e ve r t ic e s x2 a n d xp a ls o a r e n o t a d ja c e n t . Ob s e r ve t h a t if xix 2 D
wit h i 2 [3 ; p ¡ 1 ], t h e n x2xi+1 =2 D ( fo r o t h e r wis e , H = x1x2xi+1 : : : xpyx3 : : : xixx1 ) . Fr o m
t h is we h a ve , if x2x =2 D, t h e n d¡ ( x; P [x3; xp¡1]) = m ¡ 1 a n d a t le a s t m + 2 ve r t ic e s a r e n o t
d o m in a t e d b y x2 s in c e d

+ ( x2; fy; x; x1g ) = 0 , wh ic h c o n t r a d ic t s t h a t x2 is a T -ve r t e x. S o ,
we c a n a s s u m e t h a t x2x 2 D. S in c e t h e ve r t e x x is a d ja c e n t t o a ll ve r t ic e s o f P [x1; xp¡3] it
fo llo ws t h a t m = 3 . N o t e t h a t x2x4 2 D b y ( 9 ) , a n d x2; x3; x4 a r e T -ve r t ic e s . It is e a s y t o
s e e t h a t

d+ ( x2; fx1; x5; yg ) = d+ ( x3; fx; x1; x2g ) = d+ ( x4; fy; x3; x1g ) = d¡ ( x3; fx; x4; x5g ) = 0 :
Th e r e fo r e x3x5; x4x2; x1x3 2 D. S in c e x1yx3x4x2xx1 ( r e s p e c t ive ly, x2x3yx5xx4x2 ) is a

c yc le o f le n g t h n ¡ 1 = 6 , it fo llo ws t h a t x5 ( r e s p e c t ive ly, x1 ) is a T -ve r t e x. N o w fr o m
d+ ( x5; fx2; x3; x4g ) = d¡ ( x1; fx2; x3; x4g ) = 0

we h a ve x5x1 2 D. Th e r e fo r e , D is is o m o r p h ic t o t h e we ll-kn o wn d ig r a p h D7 o r is h a m ilt o -
n ia n , 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 .

Subcase 5.2.3. x2y 2 D a n d yx2 =2 D. Th e n b y Cla im 1 ( ii) we h a ve x1y 2 D a n d t h e r e
is a ve r t e x xk t o k 2 [3 ; p ¡ 3 ] wh ic h is n o t a d ja c e n t t o y ( s in c e m ¸ 3 ) . Th e n xk¡1y a n d
yxk+1 2 D b y Cla im 1 ( iii) . U s in g Cla im 3 , we o b t a in t h a t xk is n o t a d ja c e n t t o x1 a n d xp.
S in c e xk c a n n o t b e in s e r t e d in t o P [x2; xk¡1] a n d P [xk+1; xp¡1], a p p lyin g L e m m a 2 t o t h e s e
p a t h s , we o b t a in t h a t

d( xk; P [x2; xk¡1]) · k ¡ 1 ; d ( xk; P [xk+1; xp¡1]) · p ¡ k;

p + 1 · d ( xk ) = d ( xk; P [x2; xk¡1]) + d ( xk; P [xk+1; xp¡1]) + a ( xk; x )
a n d a( xk; x ) = 2 ( in o t h e r wo r d s xxk; xkx 2 D ) a n d e a c h in e qu a lit y is , in fa c t , a n e qu a lit y.
H e n c e , b y L e m m a 2 , xkx2; xp¡1xk 2 D. Fr o m xxk; xkx 2 D we o b t a in t h a t

N + ( x ) = fx1; x2; : : : ; xk; xp¡1g a n d N¡ ( x ) = fxk; xk+1; : : : ; xp¡3; xp¡1; xpg
a n d x1 : : : xk¡1yxk+1 : : : xp¡1xkxx1 is a c yc le o f le n g t h n ¡ 1 . Th e r e fo r e xp is a T -ve r t e x

a n d k = m¡ 1 . N o w we will c o n s id e r t h e ve r t e x xp. Th e n xpxi =2 D fo r a ll i 2 [k; p ¡ 1 ] [f2 g
( fo r o t h e r wis e , H = x1x2 : : : xi¡1xxp¡1xpxi : : : xp¡2yx1 wh e n i 2 [k + 1 ; p ¡ 2 ]; a n d H =
x1 : : : xi¡1yxpxi : : : xp¡1xx1 wh e n i = 2 ; k; p ¡ 1 wh ic h is a c o n t r a d ic t io n ) . Th u s , we h a ve
t h a t t h e ve r t e x xp d o e s n o t d o m in a t e a t le a s t m + 1 ve r t ic e s , wh ic h is a c o n t r a d ic t io n , s in c e
xp is a T -ve r t e x. 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 Cla im 5 .

B y Cla im 2 t h e r e is a ve r t e x xl, wh e r e l 2 [2 ; p ¡ 1 ], wh ic h is n o t a d ja c e n t t o x, a n d b y
Cla im 1 ( iii) , xl¡1x; xxl+1 2 D.

Remar k 1. L e t a ve r t e x xk, wh e r e k 2 [2 ; p¡ 1 ], is n o t a d ja c e n t t o t h e ve r t ic e s x a n d y ( in
o t h e r wo r d s d ( xk; fx; yg ) = 0 ) . Th e n xpxk; xkx1 2 D a n d N ¡ ( x ) = N ¡ ( y ) , N + ( x) = N + ( y ) .



S. Darbinyan and I. Karapetyan 1 1 3

B y Cla im 1 ( iii) , xk¡1 ! fx; yg ! xk+1, xk is a T -ve r t e x a n d xk c a n n o t b e in s e r t e d in t o
P [x1; xk¡1] a n d P [xk+1; xp]. U s in g L e m m a 2 , we o b t a in t h a t

d( xk; P [x1; xk¡1]) · k a n d d( xk; P [xk+1; xp]) · p ¡ k + 1 ;

p + 1 = d ( xk ) = d ( xk; P [x1; xk¡1]) + d ( xk; P [xk+1; xp]) · p + 1 :
Th e r e fo r e , e a c h in e qu a lit y is , in fa c t , a n e qu a lit y. H e n c e , b y L e m m a 2 , xpxk; xkx1 2 D.

N o w we s h o w t h a t N ¡ ( x ) = N¡ ( y ) a n d N + ( x) = N + ( y ) . A s s u m e t h a t t h is is n o t t h e
c a s e . L e t xix 2 D a n d xiy =2 D. Th e n xi =2 fxk¡1; xpg, a n d b y Cla im 1 ( ii) , yxi+1 2 D. S in c e
xkx1; xkxp 2 D, it is n o t d i± c u lt t o s e e t h a t H = x1x2 : : : xixxk+1 : : : xpyxi+1 : : : xkx1 wh e n
i < k ¡ 1 a n d H = x1x2 : : : xk¡1yxi+1 : : : xpxk : : : xixx1 wh e n i > k, a c o n t r a d ic t io n . To s h o w
t h a t N + ( x ) = N + ( y ) it s u ± c e s t o 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.

Claim 6. d+ ( xp¡1; fx; yg ) · 1 .
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 xp¡1x a n d xp¡1y 2 D. Th e n l · p ¡ 2 . S in c e D

is n o t h a m ilt o n ia n it fo llo ws t h a t if xxi+1 2 D o r yxi+1 2 D, t h e n xixp =2 D. Th is t o g e t h e r
wit h d¡ ( xp; fx; yg ) = 0 a n d d+ ( x; P [x2; xp¡1]) = m ¡ 1 , im p lie s t h a t a t le a s t m + 1 ve r t ic e s
d o n o t d o m in a t e xp. Cle a r ly, xp is n o t T -ve r t e x. W e will d is t in g u is h t h r e e c a s e s a c c o r d in g
a s xly 2 D o r xly =2 D a n d yxl 2 D o r xl a n d y a r e n o t a d ja c e n t .

Case 6.1. xly 2 D. Th e n d¡ ( xl; fxp; xp¡1g ) = 0 ( fo r o t h e r wis e , if xpxl 2 D, t h e n
H = x1 : : : xl¡1xxl+1 : : : xpxlyx1; a n d if xp¡1xl 2 D, t h e n x1 : : : xl¡1xxl+1 : : : xp¡1xlyx1 is
a T -c yc le , a c o n t r a d ic t io n ) . S o , b y t h e a b o ve o b s e r va t io n we h a ve t h a t xp a n d xl a r e n o t
a d ja c e n t . S in c e xp¡1xl =2 D a n d t h e ve r t ic e s xl c a n n o t b e in s e r t e d in t o P [x1; xl¡1] a n d
P [xl+1; xp¡1], u s in g L e m m a 2 , we o b t a in t h a t

d ( xl; P [x1; xl¡1]) · l a n d d( xl; P [xl+1; xp¡1]) · p ¡ l ¡ 1 :
Th e r e fo r e

p + 1 = d ( xl ) = d( xl; P [x1; xl¡1]) + d ( xl; P [xl+1; xp¡1]) + a( xl; y ) :
Fr o m t h is we c o n c lu d e t h a t yxl 2 D a n d e a c h in e qu a lit y is , in fa c t , a n e qu a lit y. H e n c e , b y
L e m m a 2 , xlx1 2 D a n d H = x1 : : : xl¡1xxl+1 : : : xpyxlx1, wh ic h is a c o n t r a d ic t io n .

Case 6.2. xly =2 D a n d yxl 2 D. Th e n xlx1 =2 D ( fo r o t h e r wis e , H =
x1 : : : xl¡1xxl+1 : : : xpyxlx1 ) a n d fr o m d( y ) = n ¡ 1 b y Cla im 1 ( ii) we h a ve , yxl+1 2 D.
S in c e xl c a n n o t b e in s e r t e d in t o P [xl+1; xp] a n d in t o P [x1; xl¡1], u s in g L e m m a 2 , we o b t a in
t h a t

d ( xl; P [x1; xl¡1]) = l ¡ 1 a n d d( xl; P [xl+1; xp]) = p ¡ l + 1 ;
a n d xpxl 2 D. B y Cla im 2 t h e r e is a ve r t e x xk, wh e r e k 2 [2 ; p ¡ 2 ], wh ic h is n o t a d ja c e n t
t o y. Th e n xk¡1y; yxk+1 2 D ( b y Cla im 1 ( iii) ) a n d xk is a T -ve r t e x. W e c a n a s s u m e t h a t
xkx =2 D ( fo r o t h e r wis e , fo r t h e ve r t e x y we wo u ld h a ve Ca s e 6 .1 ) .

A s s u m e ¯ r s t t h a t k · l ¡ 1 . Th e n fr o m xkx =2 D it fo llo ws t h a t k · l ¡ 2 .
N o w we will c o n s id e r t h e ve r t e x xk. It is e a s y t o s e e t h a t xkxp =2 D s in c e D is n o t
h a m ilt o n ia n . S in c e xp is n o t T -ve r t e x a n d yxl 2 D it fo llo ws t h a t if xpxk 2 D, t h e n
H = x1 : : : xk¡1yxl : : : xpxk : : : xl¡1xx1 is a h a m ilt o n ia n c yc le , a n d if xp¡1xk 2 D, t h e n
x1 : : : xk¡1yxl : : : xp¡1xk : : : xl¡1xx1 is a T -c yc le . 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 .
Th e r e fo r e t h e ve r t ic e s xk a n d xp a r e n o t a d ja c e n t a n d xp¡1xk =2 D. Co n s e qu e n t ly,
s in c e xk c a n n o t b e in s e r t e d in t o P [x1; xk¡1] a n d P [xk+1; xp¡1] b y L e m m a 2 we o b t a in

d ( xk; P [x1; xk¡1]) · k a n d d( xk; P [xk+1; xp¡1]) · p ¡ k ¡ 1 :
Th e r e fo r e
p + 1 = d ( xk ) = d ( xk; P [x1; xk¡1]) + d ( xk; P [xk+1; xp¡1]) + a( xk; x ) · k + p ¡ k ¡ 1 + 1 = p;
wh ic h le a d s t o a c o n t r a d ic t io n , s in c e xkx =2 D ( a( xk; x ) · 1 ) .



1 1 4 On Cycles Through Vertices of Large Semidegree in Digraphs

A s s u m e s e c o n d t h a t k ¸ l + 1 . Fr o m xly =2 D it fo llo ws t h a t k ¸ l + 2 . W e m a y a s s u m e
t h a t y is a d ja c e n t t o a ll ve r t ic e s o f P [x1; xl+1]. Th e n

fx1; x2; : : : ; xl+1g µ N + ( y ) a n d d¡ ( y; P [xl+1; xp¡1]) = m ¡ 1 :
N o w c o n s id e r t h e ve r t e x xl. It is n o t d i± c u lt t o s e e t h a t if xiy 2 D, i 2 [l + 1 ; p ¡ 1 ],

t h e n xlxi+1 =2 D ( fo r o t h e r wis e , H = x1 : : : xlxi+1 : : : xpxxl : : : xiyx1 ) . Th e r e fo r e , s in c e xl
is a T -ve r t e x a n d d+ ( xl; fx; yg ) = 0 , we o b t a in t h a t xl d o e s n o t d o m in a t e a t le a s t m + 1
ve r t ic e 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 Ca s e 6 .2 .

L e t fxl1 ; xl2; : : : xlrg b e a s e t o f ve r t ic e s wh ic h a t t h e s a m e t im e a r e n o t a d ja c e n t t o x a n d
y, wh e r e 2 · l1 < l2 < ¢ ¢ ¢ < lr · p ¡ 1 . N o t e t h a t ( b y Cla im 1 ( iii) ) fo r a ll i 2 [1 ; r] we h a ve
xli¡1x; xxli+1; xli¡1y a n d yxli+1 2 D.

Remar k 2. Th e s e t fx; y; xl1 ; xl2; : : : ; xlrg is a n in d e p e n d e n t s e t o f ve r t ic e s .
In d e e d , if xli xlj 2 D a n d li < lj , t h e n H = x1 : : : xli xlj : : : xpxxli+1 : : : xlj¡1yx1;

a n d if xli xlj 2 D a n d li > lj , t h e n b y R e m a r k 1 , xpxli 2 D a n d H =
x1 : : : xlj ¡1yxli+1 : : : xpxli xlj : : : xli¡1xx1. In e a c h c a s e we a r r ive a t a c o n t r a d ic t io n .

Case 6.3. Th e ve r t ic e s xl a n d y a r e n o t a d ja c e n t . W e c a n a s s u m e t h a t fo r a ll j 2 [2 ; p¡ 2 ]
t h e ve r t ic e s xj a n d x a r e n o t a d ja c e n t if a n d o n ly if xj a n d y a r e n o t a d ja c e n t . Th e n b y
R e m a r ks 1 a n d 2 fo r a ll i 2 [1 ; r] we h a ve

N + ( x ) = N + ( y ) = N + ( xli ) a n d N
¡ ( x ) = N¡ ( y ) = N¡ ( xli ) ;

a n d fx; y; xl1; xl2; : : : ; xlrg is a n in d e p e n d e n t s e t o f ve r t ic e s . N o t e t h a t if xxi+1 2 D, t h e n
xixp =2 D ( fo r o t h e r wis e , H = x1 : : : xixpxxi+1 : : : xp¡1yx1 ) . Fr o m t h is a n d d¡ ( xp; fx; yg ) = 0
it fo llo ws t h a t a t le a s t m + 1 ve r t ic e s d o n o t d o m in a t e xp. Th e r e fo r e , xp is n o t a T -ve r t e x.
S im ila r ly, we c a n s h o w t h a t if fxi; xi+1g ! x ( r e s p e c t ive ly, x ! fxj; xj+1g ) , t h e n xi+1
( r e s p e c t ive ly, xj ) is n o t a T -ve r t e x; a n d if xxi 2 D a n d xjx 2 D, t h e n xi¡1xj+1 =2 D. Th e
p r o o f o f Cla im 6 is c o m p le t e d .

Claim 7. xp¡1; x =2 D.
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 xp¡1x 2 D. Th e n , b y Cla im s 5 a n d 6 we h a ve

xp¡1y =2 D a n d yxp¡1 2 D. H e n c e b y Cla im 1 ( ii) , yxp 2 D. Fr o m t h is a n d Cla im 2 it fo llo ws
t h a t m ¸ 3 . Th e r e a r e t h r e e p o s s ib ilit ie s : xx2 2 D o r x a n d x2 a r e n o t a d ja c e n t o r x2x 2 D.

Case 7.1. xx2 2 D. If yx2 2 D o r y a n d x2 a r e n o t a d ja c e n t , t h e n fo r t h e c o n ve r s e
d ig r a p h o f D we h a ve t h a t Cla im 5 o r Cla im 6 is n o t t r u e . Th u s , we c a n a s s u m e t h a t
x2y 2 D a n d yx2 =2 D. Th e n x1y 2 D, b y Cla im 1 ( ii) . R e c a ll t h a t t h e r e is a ve r t e x xk wit h
k 2 [3 ; p ¡ 2 ] ( b y Cla im 2 ) wh ic h is n o t a d ja c e n t t o t h e ve r t e x y a n d h e n c e , b y Cla im 1 ( iii) ,
xk¡1y; yxk+1 2 D a n d xk is a T -ve r t e x.

N o w we will p r o ve t h a t t h e ve r t e x xk is n o t a d ja c e n t t o t h e ve r t ic e s x1 a n d xp a n d

xp¡1xk; xkx2; xkx; xxk 2 D: ( 1 3 )

S u p p o s e t h a t t h is is n o t t h e c a s e . If xkx1 2 D, t h e n H = x1yxk+1 : : : xpxx2 : : : xkx1; if x1xk 2
D, t h e n H = x1xk : : : xpxx2 : : : xk¡1yx1; if xkxp 2 D, t h e n H = x1 : : : xkxpyxk+1 : : : xp¡1xx1;
a n d ¯ n a lly if xpxk 2 D, t h e n H = x1 : : : xk¡1yxpxk : : : xp¡1xx1. 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 . Th e r e fo r e xk is n o t a d ja c e n t t o t h e ve r t ic e s x1 a n d xp. Fr o m t h is it fo llo ws
t h a t ( s in c e xk is a T -ve r t e x)

p + 1 = d ( xk ) = d( xk; P [x2; xk¡1]) + d( xk; P [xk+1; xp¡1]) + a ( xk; x) : ( 1 4 )

S in c e t h e ve r t e x xk c a n n o t b e in s e r t e d in t o P [x2; xk¡1] a n d P [xk+1; xp¡1] b y L e m m a 2 , we h a ve
d( xk; P [x2; xk¡1]) · k ¡ 1 a n d d( xk; P [xk+1; xp¡1]) · p ¡ k:



S. Darbinyan and I. Karapetyan 1 1 5

Th is t o g e t h e r wit h ( 1 4 ) im p lie s t h a t t h e a b o ve in e qu a lit ie s , in fa c t , a r e e qu a lit ie s a n d
a ( x; xk ) = 2 ( in o t h e r wo r d s xkx; xxk 2 D ) . A g a in , u s in g L e m m a 2 , we o b t a in t h a t
xp¡1xk; xkx2 2 D. ( 1 3 ) is p r o ve d .

Fr o m ( 1 3 ) a n d Cla im 2 it fo llo ws t h a t m ¸ 4 . B y ( 1 3 ) , t h e c yc le
x1 : : : xk¡1yxk+1 : : : xp¡1xkxx1 ( r e s p e c t ive ly, x2 : : : xk¡1yxk+1 : : : xpxxkx2 ) h a s le n g t h n ¡ 1
a n d d o e s n o t c o n t a in xp ( r e s p e c t ive ly, x1 ) . Th e r e fo r e , xp a n d x1 a r e T -ve r t ic e s . It is e a s y t o
s e e t h a t

if yxi 2 D wit h i 2 [2 ; p ¡ 1 ]; t h e n xi¡1xp =2 D ( 1 5 )
( o t h e r wis e , if yxi a n d xi¡1xp 2 D, t h e n x1 : : : xi¡1xpyxi : : : xp¡1xx1 is a h a m ilt o -
n ia n c yc le ) . N o t e t h a t xk¡1xp =2 D ( o t h e r wis e if xk¡1xp 2 D, t h e n b y ( 1 3 ) ,
x1 : : : xk¡1xpyxk+1 : : : xp¡1xkxx1 is a h a m ilt o n ia n c yc le , a c o n t r a d ic t io n ) . Fr o m ( 1 5 ) ,
d+ ( y; P [x2; xp¡1]) = m ¡ 2 , xk¡1xp =2 D a n d xxp =2 D it fo llo ws t h a t a t le a s t m ve r t ic e s
d o n o t d o m in a t e xp. Co n s e qu e n t ly, t h e ve r t e x y is a d ja c e n t t o a ll ve r t ic e s o f P ¡ fxkg.
H e n c e

fx1; x2; : : : ; xk¡1g ! y ! fxk+1; xk+2; : : : ; xpg; ( 1 6 )
a n d k ¡ 1 = p ¡ k = m ¡ 1 . Fr o m xk¡1xp =2 D a n d ( 1 5 ) ,( 1 6 ) we h a ve

d¡ ( xp; P [xk¡1; xp¡2]) = 0 a n d fx1; x2; : : : ; xk¡2g ! xp: ( 1 7 )

Fr o m t h is a n d ( 1 3 ) we h a ve t h a t x1 : : : xk¡2xpyxk+1 : : : xp¡1xkxx1 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 xk¡1. Th is m e a n s t h a t xk¡1 is a T -ve r t e x a n d xk¡1 c a n n o t b e in s e r t e d
in t o P [x1; xk¡2] a n d P [xk+1; xp¡1]xk.

N o w we will c o n s id e r t h e ve r t e x xk¡1 a n d c la im t h a t xk¡1 is n o t a d ja c e n t t o t h e ve r t ic e s x1
a n d xp. In d e e d , if x1xk¡1 2 D, t h e n b y ( 1 3 ) , H = x1xk¡1 : : : xpxx2 : : : xk¡2yx1; if xk¡1x1 2 D,
t h e n b y ( 1 7 ) a n d ( 1 3 ) , H = x1xpyxk+1 : : : xp¡1xkxx2 : : : xk¡1x1; if xpxk¡1 2 D, t h e n b y
( 1 6 ) , H = x1 : : : xk¡2yxpxk¡1 : : : xp¡1xx1; if xk¡1xp 2 D, t h e n b y ( 1 3 ) a n d ( 1 6 ) , H =
x1 : : : xk¡1xpyxk+1 : : : xp¡1xkxx1. In e a c h c a s e we h a ve o b t a in e d a c o n t r a d ic t io n . Th e r e fo r e
xk¡1 is n o t a d ja c e n t t o t h e ve r t ic e s x1 a n d xp. N o w b y L e m m a 2 we h a ve

p + 1 = d( xk¡1 ) = d( xk¡1; P [x2; xk¡2]) + d( xk¡1; P [xk+1; xp¡1] [ fxkg) + a( xk¡1; fx; yg ) ·

p ¡ 1 + a ( xk¡1; fx; yg ) :
It is p o s s ib le o n ly if a ( xk¡1; fx; yg ) = 2 ( i.e ., xk¡1y a n d xxk¡1 2 D s in c e yxk¡1 =2 D a n d
xk¡1x =2 D ) . It is n o t d i± c u lt t o s e e t h a t d¡ ( x1; P [xk¡1; xp¡1]) = 0 ( o t h e r wis e if xix1 2 D,
i 2 [k; p ¡ 1 ], t h e n H = x1yxi+1 : : : xpxx2 : : : xix1 ) . H e n c e xk¡2x1 2 D a n d b y ( 1 3 ) , H =
x1yxk+1 : : : xpxxk¡1xkx2 : : : xk¡2x1, wh ic h is a c o n t r a d ic t io n . Th e 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 Ca s e 7 .1 .

Case 7.2. Th e ve r t ic e s x a n d x2 a r e n o t a d ja c e n t . Th e n b y Cla im 1 ( iii) , x1x a n d
xx3 2 D. B y Cla im 4 we h a ve t h a t t h e ve r t ic e s x2 a n d y a r e a d ja c e n t . If 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, t h e n u s in g Cla im 5 we s e e t h a t x2y 2 D a n d yx2 =2 D. Th e r e fo r e , b y
Cla im 1 ( ii) , x1y 2 D s in c e y is a T -ve r t e x. N o w we will c o n s id e r t h e ve r t e x x2. N o t e t h a t x2
a ls o is a T -ve r t e x. If xpx2 2 D, t h e n H = x1yxpx2 : : : xp¡1xx1, a c o n t r a d ic t io n . S o , we c a n
a s s u m e t h a t xpx2 =2 D. B y L e m m a 2 , d ( x2; P [x3; xp]) · p¡ 2 s in c e x2 c a n n o t b e in s e r t e d in t o
P [x3; xp]. Fr o m t h is , s in c e x a n d x2 a r e n o t a d ja c e n t , yx2 =2 D a n d x2 is a T -ve r t e x, we o b t a in
t h a t x2x1 2 D. N o w it is e a s y t o s e e t h a t if yxi 2 D wit h i 2 [4 ; p], t h e n xi¡1x2 =2 D ( fo r
o t h e r wis e , H = x1yxi : : : xpxx3 : : : xi¡1x2x1 ) . Co n s e qu e n t ly, fr o m d

+ ( y; P [x4; xp]) = m ¡ 1



1 1 6 On Cycles Through Vertices of Large Semidegree in Digraphs

a n d d¡ ( x2; fx; yg) = 0 it fo llo ws t h a t a t le a s t m + 1 ve r t ic e s d o n o t d o m in a t e x2, wh ic h is a
c o n t r a d ic t io n . Th e o b t a in e d 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 Ca s e 7 .2 .

Case 7.3. x2x 2 D. Th e n x1x 2 D b y Cla im 1 ( ii) . Th e n fr o m d¡ ( x; fx1; x2; xp¡1; xpg ) =
4 we h a ve m ¸ 4 . It fo llo ws t h a t t h e r e is a l 2 [3 ; p ¡ 2 ] s u c h t h a t xl¡2x; xl¡1x; xxl+1 2 D
a n d xl a n d x a r e n o t a d ja c e n t b y Cla im 2 . N o t e t h a t wit h r e s p e c t t o t h e ve r t ic e s x2 a n d y
t h e fo llo win g s u b c a s e s a r e p o s s ib le : yx2 2 D o r x2y 2 D o r t h e ve r t ic e s y a n d x2 a r e n o t
a d ja c e n t .

Subcase 7.3.1. yx2 2 D. It is n o t d i± c u lt t o s e e t h a t t h e ve r t ic e s x1 a n d xl a r e n o t
a d ja c e n t . In d e e d , if x1xl 2 D, t h e n H = x1xl : : : xpyx2 : : : xl¡1xx1; a n d if xlx1 2 D, t h e n
H = x1xxl+1 : : : xpyx2 : : : xlx1, wh ic h is a c o n t r a d ic t io n .

W e ¯ r s t p r o ve t h a t

yxl; xlx2; xlxl¡1; xlxl¡2 2 D a n d xl¡2xl =2 D: ( 1 9 )
P r oof of (19). A s s u m e t h a t xpxl 2 D. Th e n xly =2 D ( fo r o t h e r wis e , if xly 2 D, t h e n
H = x1 : : : xl¡1xxl+1 : : : xpxlyx1 ) . S in c e x1 a n d xl a r e n o t a d ja c e n t a n d xl c a n n o t b e in s e r t e d
in t o P [x2; xl¡1] a n d P [xl+1; xp], u s in g L e m m a 2 , we s e e t h a t

p + 1 = d ( xl ) = d( xl; P [x2; xl¡1]) + d ( xl; P [xl+1; xp]) + a( xl; y ) · p + a ( xl; y ) :
It fo llo ws t h a t d( xl; P [x2; xl¡1]) = l ¡ 1 a n d a( xl; y ) = 1 . Th e r e fo r e yxl 2 D a n d xlx2 2 D

b y L e m m a 2 .
N o w a s s u m e t h a t xpxl =2 D. Th e n , s im ila r ly, a s b e fo r e we o b t a in t h a t d( xl; P [x2; xl¡1]) =

l ¡ 1 , d( xl; P [xl+1; xp]) = p ¡ l a n d a( xl; y ) = 2 ( i.e ., yxl; xly 2 D ) . B y L e m m a 2 , we h a ve
t h a t xlx2 2 D. N o w we will c o n s id e r t h e p a t h xl+1xl+2 : : : xpyx1 : : : xl¡2xl¡1 a n d t h e ve r t e x
xl in s t e a d o f y. Th e n u s in g Cla im s 6 a n d 5 we o b t a in t h a t xlxl¡1; xlxl¡2 2 D a n d xl¡2xl =2 D.
S o , in d e e d , ( 1 9 ) is s a t is ¯ e d , a s d e s ir e d .

W .l.o .g . we c a n a s s u m e t h a t xxl+2 =2 D a n d x a n d xl+2 a r e a d ja c e n t ( b e c a u s e o t h e r wis e
fo r t h e p a t h xl+1xl+2 : : : xpyx1 : : : xl¡1 we wo u ld h a ve Ca s e 7 .1 o r 7 .2 wh ic h we h a ve a lr e a d y
d e a lt wit h ) . Th e n b y Cla im 1 ( ii) we h a ve , xl+1x; xl+2x 2 D.

N o w we c o n s id e r t h e ve r t e x x1. If xix 2 D wit h i 2 [2 ; p ¡ 1 ], t h e n x1xi+1 =2 D ( fo r o t h e r -
wis e , H = x1xi+1 : : : xpyx2 : : : xixx1 ) . If x1xl+1 2 D, t h e n H = x1xl+1 : : : xpyxlx2 : : : xl¡1xx1
b y ( 1 9 ) . Ob s e r ve t h a t x2 : : : xl¡1xxl+1 : : : xpyxlx2 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 x1. Th is m e a n s t h a t x1 is a T -ve r t e x. N o w fr o m d

¡ ( x; P [x2; xp¡1]) = m ¡ 2 a n d
d+ ( x1; fy; xl+1g ) = 0 it fo llo ws t h a t t h e ve r t e x x is a d ja c e n t t o a ll ve r t ic e s o f P ¡ fxlg wh ic h
is n o t p o s s ib le s in c e m ¸ 4 , xl+1x 2 D a n d D is n o t h a m ilt o n ia n .

Subcase 7.3.2. x2y 2 D. Th e n b y Cla im s 2 a n d 1 ( iii) t h e r e is a ve r t e x xk wit h
k 2 [3 ; p ¡ 2 ] s u c h t h a t xk¡1y; yxk+1 2 D a n d y is n o t a d ja c e n t t o xk. It is e a s y t o s e e
t h a t xp a n d xk a r e n o t a d ja c e n t ( i.e ., a ( xk; xp ) = 0 ) . In d e e d , if xkxp 2 D, t h e n H =
x1 : : : xkxpyxk+1 : : : xp¡1xx1; a n d if xpxk 2 D, t h e n H = x1 : : : xk¡1yxpxk : : : xp¡1x x1, wh ic h
is a c o n t r a d ic t io n . N o w we p r o ve t h a t

xp¡1xk a n d xkx 2 D: ( 2 0 )

P r oof of (20). L e t xkx1 2 D. Th e n xxk =2 D ( s in c e , o t h e r wis e , if xxk 2 D, t h e n H =
x1 : : : xk¡1yxk+1 : : : xpxxkx1 ) a n d h e n c e , s in c e a( xk; xp ) = 0 a n d t h e p a t h s P [x1; xk¡1] a n d
P [xk+1; xp¡1] c a n n o t b e e xt e n d e d wit h xk b y L e m m a 2 we h a ve d ( xk; P [x1; xk¡1]) · k,
d( xk; P [xk+1; xp¡1]) · p ¡ k a n d

p + 1 = d( xk ) = d( xk; P [x1; xk¡1]) + d( xk; P [xk+1; xp¡1]) + a ( xk; x ) = p + 1 :
Th e r e fo r e d ( xk; P [x1; xk¡1]) = k, d( xk; P [xk+1; xp¡1]) = p ¡ k a n d a ( xk; x ) = 1 ( i.e .,

xkx 2 D ) . N o w, u s in g L e m m a 2 , we o b t a in t h a t xp¡1xk 2 D.



S. Darbinyan and I. Karapetyan 1 1 7

L e t n o w xkx1 =2 D. Th e n d( xk; P [x1; xk¡1]) · k ¡ 1 , a ( xk; x ) = 2 ( i.e ., xkx; xxk 2 D ) a n d
d( xk; P [xk+1; xp¡1]) = p ¡ k. A g a in , u s in g L e m m a 2 , we o b t a in t h a t xp¡1xk 2 D. S o , in d e e d
( 2 0 ) is s a t is ¯ e d , a s d e s ir e d .

N o w we will c o n s id e r t h e ve r t e x xp wh ic h is a T -ve r t e x s in c e x1 : : : xk¡1yxk+1 : : : xp¡1xkxx1
is a c yc le o f le n g t h n ¡ 1 . If xiy 2 D wit h i 2 [1 ; p ¡ 2 ], t h e n xpxi+1 =2 D ( fo r o t h e r wis e ,
H = x1 : : : xiyxpxi+1 : : : xp¡1xx1 ) . N o t e t h a t d

¡ ( y; P [x1; xp¡2]) = m ¡ 1 a n d xpxk+1 =2 D
( if xpxk+1 2 D, t h e n b y ( 2 0 ) , H = x1 : : : xk¡1yxpxk+1 : : : xp¡1xkxx1. It fo llo ws fr o m t h e
o b s e r va t io n a b o ve t h a t t h e ve r t e x y is a d ja c e n t t o a ll ve r t ic e s o f P ¡ fxkg. Th e r e fo r e

N¡ ( y ) = fx1; x2; : : : ; xk¡1; xpg a n d N + ( y ) = fx1; xk+1; xk+2; : : : ; xpg:
Th e n fo r t h e p a t h xk+1xk+2 : : : xpxx1x2 : : : xk¡1 a n d fo r t h e ve r t e x y b y Cla im s 5 a n d 6

we h a ve t h e c o n s id e r e d Ca s e 7 .1 .

Subcase 7.3.3. Th e ve r t ic e s y a n d x2 a r e n o t a d ja c e n t . Th e n x1y; yx3 2 D ( b y Cla im
1 ( iii) ) , x2 a n d xp a r e n o t a d ja c e n t ( b y Cla im 3 ) a n d x2 is a T -ve r t e x.

A s s u m e t h a t x2x1 2 D. Th e n xix2 =2 D if xxi+1 2 D, i 2 [3 ; p ¡ 1 ] ( fo r o t h e r wis e , H =
x1xxi+1 : : : xpyx3 : : : xix2x1 ) . N o w fr o m d

+ ( x; P [x4; xp¡1]) = m ¡ 1 a n d d¡ ( x2; fx; yg ) = 0
it fo llo ws t h a t d¡ ( x2 ) · m ¡ 1 , wh ic h is a c o n t r a d ic t io n . S o , we c a n a s s u m e t h a t x2x1 =2 D.
Th e r e fo r e

p + 1 = d( x2 ) = d ( x2; P [x3; xp¡1]) + d( x2; fx1; xg) · d( x2; P [x3; xp¡1]) + 2 :
H e n c e d( x2; P [x3; xp¡1]) = p ¡ 1 . B y L e m m a 2 , x2 c a n b e in s e r t e d in t o t h e p a t h

P [x3; xp¡1], a c o n t r a d ic t io n wh ic h c o m p le t e s t h e p r o o f o f Cla im 7 .

L e t u s n o w c o m p le t e t h e p o o f o f t h e t h e o r e m . S in c e D is n o t h a m ilt o n ia n fr o m Cla im
7 a n d R e m a r k 2 it fo llo ws t h a t fo r a n y c yc le C := x1x2 : : : x2mx1 o f le n g t h n ¡ 1 = 2 m
if x =2 V ( C ) t h e n N + ( x ) = N¡ ( x ) = fx1; x3; : : : ; x2m¡1g a n d fx2; x4; : : : ; x2m; xg is a n
in d e p e n d e n t s e t o f ve r t ic e s . Th e r e fo r e K¤m;m+1 µ D µ [Km + Km+1]¤. Th e p r o o f o f t h e
Th e o r e m is c o m p le t e .

Remar k 3. L e t D b e a d ig r a p h wit h t h e ve r t e x s e t V ( D ) = fx1; x2; x3; x4; x5; x; yg s u c h
t h a t N + ( x1 ) = fx2; x4g, N + ( x2 ) = fx; y; x3; x5g, N + ( x3 ) = N + ( x ) = N + ( y ) = fx1; x2; x4; g,
N + ( x4 ) = fx; y; x5g a n d N + ( x5 ) = fx; y; x3g. It is e a s y t o c h e c k t h a t t h e ve r t ic e s x; y; x2; x3
a n d x4 a r e T -ve r t ic e s a n d t h e ve r t ic e s x1 a n d x5 a r e n o t T -ve r t ic e s . Mo r e o ve r , t h e d ig r a p h
D is 2 -s t r o n g a n d c o n t a in s n o c yc le t h r o u g h x; y; x2; x3 a n d x4.

Refer ences

[1 ] J. B a n g -Je n s e n , G. Gu t in , D igraphs: Theory, Algorithms and Applications, 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 . 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 ath., vo l. 9 5 , p p . 7 7 -8 7 , 1 9 9 9 .

[4 ] K .A . B e r m a n , 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 " , J . Combin. Theory Ser. B , 7 4 , n o .1 , p p . 2 0 -2 7 , 1 9 9 8 .

[5 ] 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 .

[6 ] 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 ath., vo l.
1 9 , n o . 1 , p p . 8 5 -9 2 , 1 9 7 7 .



1 1 8 On Cycles Through Vertices of Large Semidegree in Digraphs

[7 ] 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 " , Akad. 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 ) .

[8 ] K h . D a r b in ya n , \ H a m ilt o n ia n a n d s t r o n g ly H a m ilt o n -c o n n e c t e d d ig r a p h s " , Akad. Nauk
Armyan. SSR D okl., vo l. 9 1 , n o . 1 , p p . 3 -6 , 1 9 9 0 ( in R u s s ia n ) .

[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 d ig r a p h s t o b e H a m ilt o n ia n " , Akad. Nauk
Armyan. SSR D okl., vo l. 9 1 , n o . 2 , p p . 5 7 -5 9 , 1 9 9 0 ( in R u s s ia n ) .

[1 0 ] 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 . Combin. Theory Ser. B , vo l.
2 0 , p p . 2 0 -4 0 , 1 9 7 6 .

[1 1 ] 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 Ser. A-B , n o . 2 5 1 , p p . 4 9 5 -4 9 7 , 1 9 6 0 .

[1 2 ] H . L i, E . Fla n d r in , 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 ath., vo l. 3 0 7 , p p . 1 2 9 1 -1 2 9 7 , 2 0 0 7 .

[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 . Graph Theory, vo l. 1 6 , n o . 1 , p p .
5 1 -5 9 , 1 9 9 2 .

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

[1 5 ] 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 ath. vo l.
1 4 5 , p p . 2 0 1 -2 1 0 , 1 9 9 5 .

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

[1 7 ] 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 roc. L ondon M ath. Soc., vo l. 3 , n o . 4 2 , p p .
2 3 1 -2 5 1 , 1 9 8 1 .

[1 8 ] 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 ath., vo l.
1 0 1 , p p . 3 1 9 -3 2 5 , 1 9 9 2 .

[1 9 ] 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 roc. L ondon M ath. Soc.,
n o . 2 4 , p p . 7 3 9 -7 5 5 , 1 9 7 2 .

Submitted 20.12.2012, accepted 14.02.2013.

Ø»Í ÏÇë³³ëïÇ׳ÝÝ»ñ áõÝ»óáÕ ·³·³ÃÝ»ñáí ³ÝóÝáÕ óÇÏÉ»ñÇ Ù³ëÇÝ

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

²Ù÷á÷áõÙ

Ü»ñϳ ³ß˳ï³ÝùáõÙ óáõÛó ¿ ïñí³Í, áñ »Ã» 2 m + 1 ·³·³Ã³ÝÇ ÏáÕÙÝáñáßí³Í
·ñ³ýÝ áõÝÇ 2 m »ñϳñáõÃÛ³Ùµ óÇÏÉ, ³å³ ³Û¹ ·ñ³ýÁ, µ³ó³éáõÃÛ³Ùµ ÙÇ ù³ÝÇ áñáß³ÏÇ
·ñ³ýÝ»ñÇ, ÝáõÛÝå»ë å³ñáõݳÏáõÙ ¿ ÏáÕÙÝáñáßí³Í óÇÏÉ, áñÝ ³ÝóÝáõÙ ¿ µáÉáñ ³ÛÝ
·³·³ÃÝ»ñáí, áñáÝó ÏÇë³³ëïÇ׳ÝÝ»ñÁ ÷áùñ ã»Ý m-Çó:

Î öèêëàõ ïðîõîäÿùèõ ÷åðåç âåðøèíû ñ áîëüøèìè
ïîëóñòåïåíÿìè

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

Àííîòàöèÿ

 íàñòîÿùåé ðàáîòå äîêàçàíî: Åñëè ( 2 m + 1 ) -âåðøèííûé îðãðàô D ñîäåðæèò
îðöèêë äëèíû 2 m, òî D òàêæå (êðîìå íåêîòîðûõ îðãðàôîâ) ñîäåðæèò îðöèêë
ïðîõîäÿùèé ÷åðåç âñå âåðøèíû ñ ïîëóñòåïåíÿìè íåìåíüøèìè m.