D:\User\sbornik_38_pdf\20.DVI


Mathematical Problems of Computer Science 38, 46{48, 2012.

On Long Cycles in Digr aphs with the M eyniel-type

Conditions

S .K h . D a r b in ya n , I.A . K a r a p e t ya n

Institute for Informatics and Automation Problems,
Armenian National Academy of Sciences

E-mails: samdarbin@ipia.sci.am, isko@ipia.sci.am

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 d ir e c t e d
g r a p h s ( d ig r a p h s ) a n d u s e B a n g -Je n s e n a n d Gu t in [1 ] a s r e fe r e n c e fo r u n d e ¯ n e d t e r m s . 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 . 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. W e will d e n o t e t h e c o m p le t e b ip a r t it e
d ig 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, q b y K¤p;q.

Me yn ie l [1 1 ] p r o ve d t h e fo llo win g t h e o r e m : If D is a s t r o n g d ig r a p h o n n ¸ 2 ve r t ic e s
a n d d( x ) + d( y ) ¸ 2 n ¡ 1 fo r a ll p a ir s o f n o n -a d ja c e n t ve r t ic e s in D, t h e n D is h a m ilt o n ia n
( s e e a ls o [1 ], [5 ] a n d [1 2 ]) .

Th o m a s s e n [1 4 ] ( fo r n = 2 k + 1 ) a n d D a r b in ya n [7 ] ( fo r n = 2 k ) p r o ve d : If D is a d ig r a p h
o n n ¸ 5 ve r t ic e s wit h m in im u m d e g r e e a t le a s t n ¡ 1 a n d wit h m in im u m s e m i-d e g r e e a t
le a s t n=2 ¡ 1 , t h e n D is h a m ilt o n ia n ( u n le s s s o m e e xt r e m a l c a s e s ) .

In e a c h a b o ve m e n t io n e d t h e o r e m s ( a s we ll a s , in we ll kn o w t h e o r e m s Gh o u ila -H o u r i
[1 0 ], W o o d a ll [1 5 ]) im p o s e s a d e g r e e c o n d it io n o n a ll p a ir s o f n o n -a d ja c e n t ve r t ic e s ( o n a ll
ve r t ic e s ) . B a n g -Je n s e n , Gu t in , L i, Gu o a n d Y e o [2 , 3 ] o b t a in e d s u ± c ie n t c o n d it io n s fo r
h a m ilt o n is it y o f d ig r a p h s in wh ic h d e g r e e c o n d it io n s r e qu ir in g o n ly fo r s o m e p a ir s o f n o n -
a d ja c e n t ve r t ic e s . N a m e ly, t h e y p r o ve d t h e fo llo win g t h e o r e m s ( in a ll t h r e e t h e o r e m s D is a
s t r o n g d ig r a p h o n n ¸ 2 ve r t ic e s ) .
T heor em A [2 ]. If minfd ( x ) ; d ( y ) g ¸ n ¡ 1 a n d d( x ) + d( y ) ¸ 2 n ¡ 1 fo r e ve r y p a ir o f
n o n -a d ja c e n t ve r t ic e s x, y wit h a c o m m o n in -n e ig h b o u r , t h e n D is h a m ilt o n ia n .
T heor em B [2 ]. If minfd+ ( x ) + d¡ ( y ) ; d¡ ( x ) + d+ ( y ) g ¸ n fo r e ve r y p a ir o f n o n -a d ja c e n t
ve r t ic e s x, y wit h a c o m m o n o u t -n e ig h b o u r o r a c o m m o n in -n e ig h b o u r , t h e n D is h a m ilt o n ia n .
T heor em C [3 ]. If minfd+ ( x) + d¡ ( y ) ; d¡ ( x ) + d+ ( y ) g ¸ n ¡ 1 a n d d( x ) + d ( y ) ¸ 2 n ¡ 1
fo r e ve r y p a ir o f n o n -a d ja c e n t ve r t ic e s x, y wit h a c o m m o n o u t -n e ig h b o u r o r a c o m m o n
in -n e ig h b o u r , t h e n D is h a m ilt o n ia n .

N o t e t h a t Th e o r e m C g e n e r a liz e s Th e o r e m B . In [9 , 1 3 , 6 , 8 ] it wa s s h o wn t h a t if t h e
s t r o n g d ig r a p h D s a t is ¯ e s t h e c o n d it io n o f t h e t h e o r e m o f Gh o u ila -H o u r i [1 0 ] ( W o o d a ll [1 5 ],
Me yn ie l [1 1 ], Th o m a s s e n a n d D a r b in ya n [1 4 , 7 ]) , t h e n D is p a n c yc lic ( u n le s s s o m e e xt r e m a l
c a s e s , wh ic h a r e c h a r a c t e r iz e d ) . It is n o t d i± c u lt t o c h e c k t h a t t h e d ig r a p h s K¤n=2;n=2 a n d
K¤n=2;n=2¡feg, wh e r e n is e ve n a n d e is a n a r c o f K¤n=2;n=2, s a t is fy t h e c o n d it io n s o f Th e o r e m A
( B , C) a n d h a s n o c yc le o f o d d le n g t h . Mo r e o ve r , if in Th e o r e m s A ( B , C) t h e d ig r a p h D h a s
n o p a ir o f n o n -a d ja c e n t ve r t ic e s wit h a c o m m o n in -n e ig h b o u r a n d a c o m m o n o u t -n e ig h b o u r ,

4 6



S. Darbinyan, I. Karapetyan 4 7

t h e n D is a lo c a lly s e m ic o m p le t e d ig r a p h , a n d in [4 ], B a n g -Je n s e n , Gu t in a n d V o lkm a n n
c h a r a c t e r iz e t h o s e s t r o n g lo c a lly s e m ic o m p le t e d ig r a p h s wh ic h a r e n o t p a n c yc lic .

It is n a t u r a l t o s e t t h e fo llo win g p r o b le m :
P r oblem. Ch a r a c t e r iz e t h o s e d ig r a p h s wh ic h s a t is fy t h e c o n d it io n s o f Th e o r e m A ( B , C) ,
b u t a r e n o t p a n c yc lic .

To in ve s t ig a t e t h a t a g ive n d ig r a p h D is p a n c yc lic , in [9 , 1 3 , 6 , 8 ] it wa s p r o ve d t h e
e xis t e n c e o f c yc le s o f le n g t h jV ( D ) j ¡ 1 a n d jV ( D ) j ¡ 2 , a n d t h e n u s in g t h e c o n s t r u c t io n s o f
t h e s e c yc le s it wa s p r o ve d t h a t D is p a n c yc lic wit h s o m e e xc e p t io n s .

W e p r o ve t h r e e r e s u lt 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 P r o b le m .
T heor em 1. L e t D b e a s t r o n g d ig r a p h o n n ve r t ic e s wit h m in im u m s e m i-d e g r e e a t le a s t
t wo . If D s a t is ¯ e s t h e c o n d it io n s o f Th e o r e m A , t h e n e it h e r D c o n t a in s a c yc le o f le n g t h n¡ 1
o r n is e ve n a n d D is is o m o r p h ic t o c o m p le t e b ip a r t it e d ig r a p h K¤n=2;n=2 o r K

¤
n=2;n=2 ¡ feg,

wh e r e e is a n a r c o f K¤n=2;n=2.
T heor em 2. L e t D b e a s t r o n g d ig r a p h o n n ¸ 4 ve r t ic e s , wh ic h is n o t d ir e c t e d c yc le o f
le n g t h n. If D s a t is ¯ e s t h e c o n d it io n s o f Th e o r e m B , t h e n e it h e r D c o n t a in s a c yc le o f le n g t h
n ¡ 1 o r n is e ve n a n d D is o m o r p h ic t o c o m p le t e b ip a r t it e d ig r a p h K¤n=2;n=2.

N o t e t h a t Th e o r e m 1 is s h a r p , in t h e s e n s e t h a t fo r a ll n ¸ 6 t h e r e is a s t r o n g d ig r a p h D
o n n ve r t ic e s wh ic h h a s m in im u m s e m i-d e g r e e o n e a n d s a t is ¯ e s t h e c o n d it io n o f Th e o r e m 1 ,
b u t c o n t a in n o c yc le o f le n g t h n ¡ 1 . To s e e t h is , it is s u ± c ie n t t o c o n s id e r t h e d ig r a p h Dn;m
wh ic h wa s d e ¯ n e d in [1 3 ] ( s e e a ls o [1 ].p .3 0 0 ) . W h e n m = n ¡ 1 , t h e n Dn;m h a s m in im u m
s e m i-d e g r e e o n e a n d s a t is ¯ e s t h e c o n d it io n s o f Th e o r e m 1 b u t h a s n o c yc le o f le n g t h n ¡ 1 .

W e b e lie ve Th e o r e m 2 c a n b e g e n e r a liz e d t o t h e fo llo win g
Conjectur e. L e t D b e a s t r o n g d ig r a p h o n n ¸ 4 ve r t ic e s . If D s a t is ¯ e s t h e c o n d it io n s o f
Th e o r e m C, t h e n D c o n t a in s a c yc le o f le n g t h n ¡ 1 m a yb e e xc e p t s o m e d ig r a p h s wh ic h h a s
a " s im p le " c h a r a c t e r iz a t io n .

S u p p o r t fo r t h e c o n je c t u r e we p r o ve t h e fo llo win g .
T heor em 3. L e t D b e a s t r o n g d ig r a p h wit h n ¸ 2 ve r t ic e s , wh ic h is n o t d ir e c t e d c yc le . If
D s a t is ¯ e s t h e c o n d it io n s o f Th e o r e m C, t h e n D c o n t a in s a c yc le o f le n g t h n ¡ 2 o r n ¡ 1 .

R eferences

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

[2 ] J. B a n g -Je n s e n , G. Gu t in , H . L i, S u ± c ie n t c o n d it io n s fo r a d ig r a p h t o b e h a m ilt o n ia n ,
J. Gr a p h Th e o r y 2 2 ( 2 ) ( 1 9 9 6 ) 1 8 1 -1 8 7 .

[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 is c r e t e A p p lie d Ma t h ., 9 5 ( 1 9 9 9 ) 7 7 -8 7 .

[4 ] J. B a n g -Je n s e n , Y . Gu o , L . V o lkm a n n , A c la s s ī c a t io n o f lo c a lly s e m ic o m p le t e d i-
g r a p h s . 1 5 t h B r it is h Co m b in a t o r ia l Co n fe r e n c e ( S t ir lin g , 1 9 9 5 ) . D is c r e t e Ma t h .. 1 6 7 / 1 6 8
( 1 9 9 7 ) 1 0 1 -1 1 4 .

[5 ] J.A . B o n d y, C. Th o m a s s e n , A s h o r t p r o o f o f Me yn ie l's t h e o r e m , D is c r e t e Ma t h . 1 9
( 1 9 7 7 ) 1 9 5 -1 9 7 .

[6 ] S .K h . D a r b in ya n , P a n c yc lic a n d p a n c o n n e c t e d d ig r a p h s , P h . D . Th e s is , In s t it u t e
Ma t h e m a t ic i A ka d . N a u k B S S R , Min s k, 1 9 8 1 ( s e e a ls o P a n c yc lic it y o f d ig r a p h s wit h t h e
Me yn ie l c o n d it io n , S t u d ia S c i. Ma t h . H u n g a r ., 2 0 ( 1 -4 ) ( 1 9 8 5 ) 9 5 -1 1 7 , in R u s s ia n ) .



4 8 On Long Cycles in Digraphs with the Meyniel-type Conditions

[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 , A ka d . N a u k A r m ya n . S S R D o kl. 8 2 ( 1 ) ( 1 9 8 6 ) 6 -8 ( 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 ] S .K h . D a r b in ya n , On t h e p a n c yc lic it 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 , A ka d . N a u k
A r m ya n . S S R D o kl. 8 3 ( 3 ) ( 1 9 8 6 ) 9 9 -1 0 1 ( s e e a ls o a r X iv: 1 1 1 1 .1 8 4 1 v1 [m a t h .CO] 8 N o v
2 0 1 1 ) .

[9 ] 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. Co m b in . Th e o r y S e r . B 2 0
( 1 9 7 6 ) 2 0 -4 0 .

[1 0 ] 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 . A c a d . S c i. P a r is S e r . A -B 2 5 1 ( 1 9 6 0 ) 4 9 5 -4 9 7 .

[1 1 ] 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. Co m b in . Th e o r y S e r . B 1 4 ( 1 9 7 3 ) 1 3 7 -1 4 7 .

[1 2 ] M. Ove r b e c k-L a r is c h , H a m ilt o n ia n p a t h s in o r ie n t e d g r a p h s , J. Co m b in . Th e o r y S e r .
B 2 1 ( 1 ) ( 1 9 7 6 ) 7 6 -8 0 .

[1 3 ] C. Th o m a s s e n , A n Or e -t yp e c o n d it io n im p lyin g a d ig r a p h t o b e p a n c yc lic , D is c r e t e
Ma t h . 1 9 ( 1 ) ( 1 9 7 7 ) 8 5 -9 2 .

[1 4 ] 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 r o c . L o n d o n Ma t h . S o c . ( 3 ) 4 2 ( 1 9 8 1 )
2 3 1 -2 5 1 .

[1 5 ] 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 r o c . L o n d o n Ma t h . S o c .
2 4 ( 1 9 7 2 ) 7 3 9 -7 5 5 .