D:\Sbornik_45_TeX\...\7_17.DVI


Mathematical Problems of Computer Science 46, 7{17, 2016.

On pr e-H amiltonian Cycles in B alanced B ipar tite

Digr aphs

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 strongly connected balanced bipartite directed graph of order 2a ¸ 10.
Let x; y be distinct vertices in D. fx; yg dominates a vertex z if x ! z and y ! z; in
this case, we call the pair fx; yg dominating. In this paper we prove:

If maxfd(x); d(y)g ¸ 2a¡2 for every dominating pair of vertices fx; yg, then either
the underlying graph of D is 2-connected or D contains a cycle of length 2a ¡ 2 or D
is isomorphic to one digraph of order ten.

Keywords: Digraphs, Cycles, Hamiltonian cycles, Bipartite balanced digraph,
Pancyclic, Even pancyclic.

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

W e c o n s id e r d ir e c t e d g r a p h s ( d ig r a p h s ) in t h e s e n s e o f [1 ]. A c yc le o f a d ig r a p h D is c a lle d
H a m ilt o n ia n if it c o n t a in s a ll t h e ve r t ic e s o f D. 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 d ig r a p h D o f o r d e r n 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 a n d p a n c yc lic if it c o n t a in s c yc le s o f e ve r y le n g t h k, 3 · k · n.
Fo r g e n e r a l d ig r a p h s t h e r e a r e s e ve r a l s u ± c ie n t c o n d it io n s fo r e xis t e n c e o f H a m ilt o n ia n c yc le s
in d ig r a p h s . In t h is p a p e r , we will b e c o n c e r n e d wit h t h e d e g r e e c o n d it io n s .

Th e we ll-kn o wn a n d c la s s ic a l a r e Gh o u ila -H o u r i's , N a s h -W illia m s ', W o o d a ll's , Me yn ie l's
a n d Th o m a s
s e n 's t h e o r e m s ( s e e , e .g ., [2 ]- [6 ]) . Th e r e a r e a n a lo g o u s r e s u lt s o f t h e a b o ve -m e n t io n e d
t h e o r e m s fo r t h e p a n c yc lic it y o f d ig r a p h s ( s e e , e .g ., [7 -1 2 ]) . E a c h o f t h e o r e m s ( [2 ]-[6 ]) im p o s e s
a d e g r e e c o n d it io n o n a ll p a ir s o f n o n a d ja c e n t ve r t ic e s ( o r o n a ll ve r t ic e s ) .

In [1 3 ] a n d [1 4 ], s o m e s u ± c ie n t c o n d it io n s we r e d e s c r ib e d fo r a d ig r a p h t o b e H a m ilt o n ia n ,
in wh ic h a d e g r e e c o n d it io n is r e qu ir e d 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 . L e t u s
r e c a ll o n ly t h e fo llo win g t h e o r e m o f t h e m .
T heor em 1.1: ( B a n g -Je n s e n , Gu t in , H .L i [1 3 ]) . L et D be a strongly connected digraph of
order n ¸ 2 . Suppose that minfd( x ) ; d ( y ) g ¸ n ¡ 1 and d( x ) + d( y ) ¸ 2 n ¡ 1 for any pair
of nonadjacent vertices x; y with a common in-neighbor. Then D is Hamiltonian.

A c yc le o f a n o n -b ip a r t it e d ig r a p h D is c a lle d p r e -H a m ilt o n ia n if it c o n t a in s a ll t h e
ve r t ic e s o f D e xc e p t o n e . Th e c o n c e p t o f p r e -H a m ilt o n ia n c yc le fo r t h e b a la n c e d b ip a r t it e
d ig r a p h s is t h e fo llo win g :

7



8 On pre-Hamiltonian Cycles in Balanced Bipartite Digraphs

A c yc le o f a b a la n c e d b ip a r t it e d ig r a p h D is c a lle d p r e -H a m ilt o n ia n if it c o n t a in s a ll t h e
ve r t ic e s o f D e xc e p t t wo .

A d ig r a p h D is c a lle d b ip a r t it e if t h e r e e xis t s a p a r t it io n X, Y o f it s ve r t e x s e t in t o t wo
p a r t it e s e t s s u c h t h a t e ve r y a r c o f D h a s it s e n d -ve r t ic e s in d i®e r e n t p a r t it e s e t s . It is c a lle d
b a la n c e d if jXj = jY j.

Th e r e a r e r e s u lt s a n a lo g o u s t o t h e t h e o r e m s o f Gh o u ila -H o u r i, N a s h -W illia m s , W o o d a ll,
Me yn ie l a n d Th o m a s s e n fo r b a la n c e d b ip a r t it e d ig r a p h s ( s e e e .g ., [1 5 ]) a n d t h e p a p e r s c it e d
t h e r e .

L e t x; y b e a p a ir o f d is t in c t ve r t ic e s in a d ig r a p h D. W e c a ll t h e p a ir fx; yg d o m in a t in g ,
if t h e r e is a ve r t e x z in D s u c h t h a t x ! z a n d y ! z.

A n a n a lo g u e o f Th e o r e m 1 .1 fo r b ip a r t it e d ig r a p h s wa s g ive n b y R . W a n g [1 6 ] a n d r e c e n t ly
s t r e n g t h e n e d b y t h e a u t h o r [1 7 ].
T heor em 1.2: ( R . W a n g [1 6 ]) . L et D be a strongly connected balanced bipartite digraph of
order 2 a, where a ¸ 1 . Suppose that, for every dominating pair of vertices fx; yg, either
d( x ) ¸ 2 a ¡ 1 and d( y ) ¸ a + 1 or d ( y ) ¸ 2 a ¡ 1 and d( x ) ¸ a + 1 . Then D is Hamiltonian.

L e t D b e a b a la n c e d b ip a r t it e d ig r a p h o f o r d e r 2 a ¸ 4 . Fo r in t e g e r k ¸ 0 , we s a y t h a t
D s a t is ¯ e s c o n d it io n Bk wh e n maxfd( x ) ; d( y ) g ¸ 2 a ¡ 2 + k fo r e ve r y p a ir o f d o m in a t in g
ve r t ic e s x a n d y.
T heor em 1.3: ( D a r b in ya n [1 7 ]) . L et D be a strongly connected balanced bipartite digraph
of order 2 a, where a ¸ 4 . Suppose that D satis¯es condition B1, i.e., for every dominating
pair of vertices fx; yg, either d ( x ) ¸ 2 a ¡ 1 or d( y ) ¸ 2 a ¡ 1 . Then either D is Hamiltonian
or isomorphic to the digraph D ( 8 ) (for the de¯nition of D ( 8 ) , see E xample 1).

A b a la n c e d b ip a r t it e d ig r a p h o f o r d e r 2 m is e ve n p a n c yc lic if it c o n t a in s a c yc le o f le n g t h
2 k fo r a n y 2 · k · m.

A n e ve n p a n c yc lic ve r s io n o f Th e o r e m 1 .3 wa s p r o ve d in [1 8 ].
T heor em 1.4: ( D a r b in ya n [1 8 ]) . L et D be a strongly connected balanced bipartite digraph
of order 2 a ¸ 8 other than the directed cycle of length 2 a. If D satis¯es condition B1, i.e.,
maxfd( x ) ; d( y ) g ¸ 2 a¡ 1 for every dominating pair of vertices fx; yg, then either D contains
cycles of all even lengths less than or equal to 2 a or D is isomorphic to digraph D ( 8 ) .
T heor em 1.5: ( D a r b in ya n [1 8 ]) . L et D be a strongly connected balanced bipartite digraph
of order 2 a ¸ 8 , which contains a pre-Hmiltonian cycle (i.e., a cycle of length 2 a ¡ 2 ).
If D satis¯es condition B0, i.e., maxfd( x ) ; d( y ) g ¸ 2 a ¡ 2 for every dominating pair of
vertices fx; yg, then for any k, 1 · k · a ¡ 1 , D contains a cycle of length 2 k for every k,
1 · k · a ¡ 1 .

In vie w o f Th e o r e m 1 .5 it s e e m s qu it e n a t u r a l t o a s k wh e t h e r a b a la n c e d b ip a r t it e d ig r a p h
o f o r d e r 2 a in wh ic h maxfd ( x) ; d ( y ) g ¸ 2 a ¡ 2 fo r e ve r y d o m in a t in g p a ir o f ve r t ic e s fx; yg
c o n t a in s a p r e -H a m ilt o n ia n c yc le ( i.e ., a c yc le o f le n g t h 2 a ¡ 2 ) .

Th e u n d e r lyin g g r a p h o f a d ig r a p h D is t h e u n iqu e g r a p h s u c h t h a t it c o n t a in s a n e d g e
xy if x ! y o r y ! x ( o r b o t h ) .

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 .
T heor em 1.6: L et D be a strongly connected balanced bipartite digraph of order 2 a ¸ 1 0
with partite sets X and Y . Assume that D satis¯es condition B0. Then either the underlying
graph of D is 2-connected or D contains a cycle of length 2 a ¡ 2 unless D is isomorphic to
the digraph D ( 1 0 ) (for the de¯nition of D ( 1 0 ) , see E xample 2).



S. Darbinyan 9

2 . Te r m in o lo g y a n d N o t a t io n 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 ].
In t h is p a p e r we c o n s id e r ¯ n it e d ig r a p h s wit h o u t lo o p s a n d m u lt ip le a r c s . Fo r a d ig r a p h

D, we d e n o t e b y V ( D ) t h e ve r t e x s e t o f D a n d b y A( D ) t h e s e t o f a r c s in D. Th e o r d e r
o f D is t h e n u m b e r o f it s ve r t ic e s . Th e a r c o f a d ig r a p h D d ir e c t e d fr o m x t o y is d e n o t e d
b y xy o r x ! y. Th e n o t a t io n x $ y m e n a s t h a t x ! y a n d y ! x ( x $ y is c a lle d
2 -c yc le ) . 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 wit h e n d -ve r t ic e s x a n d y. 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 s o m e t im e s 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
n o t a t io n A $ B m e a n s t h a t A ! B a n d B ! A. Th e o u t -n e ig h b o u r h o o d o f a ve r t e x x
is t h e s e t N + ( x ) = fy 2 V ( D ) =xy 2 A( D ) g a n d N¡ ( x ) = fy 2 V ( D ) =yx 2 A( D ) g is t h e
in -n e ig h b o u r h o o d o f x. S im ila r ly, if A µ V ( D ) , t h e n N + ( x; A ) = fy 2 A=xy 2 A( D ) g
a n d N¡ ( x; A ) = fy 2 A=yx 2 A ( D ) g. Th e o u t -d e g r e e o f x is d+ ( x ) = jN + ( x ) j a n d
d¡ ( x ) = jN¡ ( x ) j is t h e in -d e g r e e o f x. S im ila r ly, d+ ( x; A) = jN + ( x; A) j a n d d¡ ( x; A) =
jN¡ ( x; A ) j. Th e d e g r e e o f t h e ve r t e x x in D is d e ¯ n e d a s d ( x) = d+ ( x ) + d¡ ( x ) ( s im ila r ly,
d( x; A) = d+ ( x; A) + d¡ ( x; A ) ) . Th e 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 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 ) . 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 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 D is a H a m ilt o n ia n c yc le . A d ig r a p h D is s t r o n g ly 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.

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 ) . 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.

A d ig r a p h D is c a lle d a b ip a r t it e d ig r a p h if t h e r e e xis t s a p a r t it io n X, Y o f V ( D ) in t o
t wo p a r t it e s e t s s u c h t h a t e ve r y a r c o f D h a s it s e n d -ve r t ic e s in d i®e r e n t p a r t it e s e t s . It is
c a lle d b a la n c e d if jXj = jY j.

3 . E xa m p le s

E xample 1. L e t D ( 1 0 ) b e a 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 X = fx0; x1; x2; x3; x4g
a n d Y = fy0; y1; y2; y3; y4g s a t is fyin g t h e fo llo win g c o n d it io n s : t h e in d u c e d s u b d ig r a p h
hfx1; x2; x3; y0; y1gi is a 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 fx1; x2; x3g a n d fy0; y1g;
fx1; x2; x3g ! fy2; y3; y4g; x4 $ y1; x0 $ y0 a n d xi $ yi+1 fo r a ll i 2 [1 ; 3 ]. D ( 1 0 ) c o n t a in s
n o o t h e r a r c s .

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 D ( 1 0 ) is s t r o n g ly c o n n e c t e d a n d s a t is ¯ e s
c o n d it io n B0, b u t t h e u n d e r lyin g g r a p h o f D ( 1 0 ) is n o t 2 -c o n n e c t e d a n d D ( 1 0 ) h a s n o c yc le
o f le n g t h 8 . ( It fo llo ws fr o m t h e fa c t s t h a t d ( x0 ) = d( x4 ) = 2 a n d x0 ( x4 ) is o n 2 -c yc le ) .
E xample 2. L e t D ( 8 ) b e a 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 X = fx0; x1; x2; x3g a n d Y =
fy0; y1; y2; y3g s a t is fyin g t h e fo llo win g c o n d it io n s : t h e in d u c e d s u b d ig r a p h hfx1; x2; y0; y1; y3gi
is a 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 fx1; x2g a n d fy0; y1; y3g; fx1; x2; x3g !
fy2; y3; y4g; x3 $ y3; x0 $ y0 a n d x0 $ y1 a n d D ( 8 ) c o n t a in s n o o t h e r a r c s .

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 D ( 8 ) is s t r o n g ly c o n n e c t e d a n d s a t is ¯ e s



1 0 On pre-Hamiltonian Cycles in Balanced Bipartite Digraphs

c o n d it io n B0, b u t t h e u n d e r lyin g g r a p h o f D ( 8 ) is n o t 2 -c o n n e c t e d a n d D ( 8 ) h a s n o c yc le o f
le n g t h 6 .

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

P r oof of T heor em 1.6: S u p p o s e , o n t h e c o n t r a r y, t h a t t h e u n d e r lyin g g r a p h o f D is n o t
2 -c o n n e c t e d a n d D c o n t a in s n o c yc le o f le n g t h 2 a ¡ 2 . Th e n V ( D ) = A [ B [ fug, wh e r e
A a n d B a r e n o n e m p t y d is jo in t s u b s e t s o f ve r t ic e s o f D, t h e ve r t e x u is n o t in A [ B a n d
t h e r e a r e n o a r c s b e t we e n A a n d B. S in c e D is s t r o n g , t h e r e a r e ve r t ic e s x 2 A a n d x0 2 B
s u c h t h a t fx; x0g ! u, i.e ., fx; x0g is a d o m in a t in g p a ir . N o t e t h a t x a n d x0 b e lo n g t o t h e
s a m e p a r t it e s e t , s a y X. Th e n u 2 Y . B y c o n d it io n B0 we h a ve maxfd( x ) ; d( x0 ) g ¸ 2 a ¡ 2 .
W it h o u t lo s s o f g e n e r a lit y, we a s s u m e t h a t d ( x ) ¸ 2 a ¡ 2 . Fr o m t h is a n d t h e fa c t t h a t t h e r e
a r e n o a r c s b e t we e n A a n d B it fo llo ws t h a t a ¡ 2 · jY \ Aj · a ¡ 1 .

P u t Y1 := Y \ A. W e will c o n s id e r t h e c a s e s jY1j = a ¡ 2 a n d jY1j = a ¡ 1 s e p a r a t e ly.
Case 1: jY1j = a ¡ 2 .

Th e n jY \ Bj = 1 . L e t Y1 := fy1; y2; : : : ; ya¡2g a n d Y \ B := fy0g. It is n o t d i± c u lt
t o c h e c k t h a t t h e ve r t e x x a n d e ve r y ve r t e x o f Y1 [ fug fo r m a 2 -c yc le , i.e ., x $ Y1 [ fug.
Th e r e fo r e , e ve r y p a ir o f d is t in c t ve r t ic e s o f Y1 [ fug is a d o m in a t in g p a ir . Th is m e a n s t h a t
Y1 [ fug h a s a t le a s t a ¡ 2 ve r t ic e s o f d e g r e e a t le a s t 2 a ¡ 2 ( m a yb e e xc e p t , s a y ya¡2, o r u ) .
Th e n d ( y1 ) ¸ 2 a¡ 2 , s in c e a ¸ 5 . Fr o m t h is it fo llo ws t h a t jX \Aj = a¡ 1 a n d X \B = fx0g
s in c e t h e r e a r e n o a r c s b e t we e n y1 a n d B.

P u t X1 := fx1; x2; : : : ; xa¡1g, wh e r e x1 = x. Th e r e fo r e , B = fx0; y0g. S in c e D is s t r o n g
a n d s in c e y0 is n o t a d ja c e n t t o a n y ve r t e x o f X1, it fo llo ws t h a t y0 $ x0, u ! x0, d( x0 ) = 4
a n d d( y0 ) = 2 . B y c o n d it io n B0, we h a ve d ( u ) ¸ 2 a ¡ 2 s in c e fu; y0g ! x0.

A s s u m e ¯ r s t t h a t d ( yi ) ¸ 2 a ¡ 2 fo r a ll i 2 [1 ; a ¡ 2 ]. Th e n Y1 $ X1, s in c e t h e r e a r e n o
a r c s b e t we e n Y1 a n d fx0g, i.e ., t h e in d u c e d s u b d ig r a p h DhY1 \ X1i is a 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 X1 a n d Y1. S in c e d( u ) ¸ 2 a ¡ 2 , it fo llo ws t h a t t h e ve r t e x u a n d
a t le a s t a ¡ 2 ve r t ic e s o f X1 fo r m a 2 c yc le . N o w we c a n c h o o s e a ve r t e x o f X1 o t h e r t h a n
x, s a y x2, s u c h t h a t u $ x2. Th e r e fo r e , x1ux2y2x3 : : : xa¡2ya¡2xa¡1y1x1 is a c yc le o f le n g t h
2 a ¡ 2 , wh ic h c o n t r a d ic t s t h e s u p p o s it io n t h a t D c o n t a in s n o c yc le o f le n g t h 2 a ¡ 2 .

A s s u m e s e c o n d t h a t Y1 h a s a ve r t e x, s a y ya¡2, o f d e g r e e a t m o s t 2 a ¡ 3 . Th e n fr o m
c o n d it io n B0 it fo llo ws t h a t d( yi ) ¸ 2 a ¡ 2 fo r a ll i 2 [1 ; a ¡ 3 ] s in c e x $ Y1 [ fug. Th is
im p lie s t h a t t h e s u b d ig r a p h DhX1 [ fy1; y2; : : : ; ya¡3gi is a 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 X1 a n d fy1; y2; : : : ; ya¡3g. In p a r t ic u la r , y1 $ X1. Th e n e ve r y p a ir o f d is t in c t
ve r t ic e s o f X1 is a d o m in a t in g p a ir . Co n d it io n B0 im p lie s t h a t X1 h a s a t le a s t a ¡ 2 ve r t ic e s ,
s a y x1; x2; : : : ; xa¡2 , o f d e g r e e a t le a s t 2 a ¡ 2 . Th e n

fx1; x2; : : : ; xa¡2g $ Y1 [ fug;
in p a r t ic u la r ya¡2 $ fx1; x2; : : : ; xa¡2g a n d u $ fx1; x2; : : : ; xa¡2g. Th e r e fo r e ,
y1xa¡1y2x2y3x3 : : : ya¡2 xa¡2ux1y1 is a c yc le o f le n g t h 2 a ¡ 2 , wh ic h is a c o n t r a d ic t io n .
Case 2: jY1j = a ¡ 1 .

L e t n o w Y1 := fy1; y2; : : : ; ya¡1g. Th e n Y \ B = ;, i.e ., B µ X. S in c e D is s t r o n g ,
fr o m c o n d it io n B0 it fo llo ws t h a t B = fx0g, u $ x0 a n d jX \ Aj = a ¡ 1 . L e t n o w
X1 := X \ A = fx1; x2; : : : ; xa¡1g, wh e r e x1 = x ( r e c a ll t h a t x1 ! u ) .

If d ( yi ) ¸ 2 a ¡ 2 fo r a ll i 2 [1 ; a ¡ 1 ] t h e n t h e s u b d ig r a p h DhX1 [ Y1i is a 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 X1 a n d Y1. Th e r e fo r e , D c o n t a in s a c yc le o f le n g t h
2 a ¡ 2 , a c o n t r a d ic t io n .



S. Darbinyan 1 1

A s s u m e t h e r e fo r e t h a t Y1 h a s a ve r t e x o f d e g r e e a t m o s t 2 a ¡ 3 . Ob s e r ve t h a t Y1 m a y
h a s a t m o s t t h r e e ve r t ic e s o f d e g r e e le s s t h a n 2 a ¡ 2 s in c e d( x1 ) ¸ 2 a ¡ 2 ( fo r o t h e r wis e Y1
c o n t a in s t wo ve r t ic e s , s a y v a n d z, s u c h t h a t fv; zg ! x1 a n d maxfd( v ) ; d ( z ) g · 2 a ¡ 3 ,
wh ic h c o n t r a d ic t s c o n d it io n B0 ) . W e will c o n s id e r t h e fo llo win g fo u r s u b c a s e s d e p e n d in g o n
t h e n u m b e r o f ve r t ic e s o f Y1, wh ic h h a ve d e g r e e a t m o s t 2 a ¡ 3 .
Subcase 2.1: Y1 h a s e xa c t ly o n e ve r t e x o f d e g r e e le s s t h a n 2 a ¡ 2 .

A s s u m e , wit h o u t lo s s o f g e n e r a lit y, t h a t d( ya¡1 ) · 2 a ¡ 3 a n d d( yi ) ¸ 2 a ¡ 2 fo r a ll
i 2 [1 ; a ¡ 2 ]. Th e n it is e a s y t o s e e t h a t t h e s u b d ig r a p h DhX1 [ Y1 n fya¡1gi is a 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 X1 a n d Y1 n fya¡1g s in c e d( x0; Y1 ) = 0 . Fr o m s t r o n g
c o n n e c t e d n e s s o f D it fo llo ws t h a t d+ ( u; X1 ) ¸ 1 . If u ! xi fo r s o m e i 2 [2 ; a ¡ 1 ], t h e n b y
s ym m e t r y b e t we e n t h e ve r t ic e s x2; x3; : : : ; xa¡1, we c a n a s s u m e t h a t u ! x2. Th e n it is e a s y
t o s e e t h a t ux2y2x3 : : : ya¡2xa¡1y1x1u is a c yc le o f le n g t h 2 a ¡ 2 , wh ic h is a c o n t r a d ic t io n .
A s s u m e t h e r e fo r e t h a t

d+ ( u; fx2; x3; : : : xa¡1g ) = 0 : ( 1 )
Th e n u ! x1, d+ ( ya¡1 ) ¸ 1 a n d d¡ ( ya¡1 ) ¸ 1 , s in c e D is s t r o n g . If t h e r e e xis t t wo
d is t in c t ve r t ic e s o f X1, s a y x1 a n d x2, s u c h t h a t x1 ! ya¡1 a n d ya¡1 ! x2, t h e n t h e
c yc le x1ya¡1x2y2x3 : : : xa¡2ya¡2xa¡1y1x1 is a c yc le o f le n g t h 2 a ¡ 2 , a c o n t r a d ic t io n . A s s u m e
t h e r e fo r e t h a t t h e r e a r e n o t wo d is t in c t ve r t ic e s xi a n d xj o f X1 s u c h t h a t xi ! ya¡1 a n d
ya¡1 ! xj. Th e n d+ ( ya¡1 ) = d¡ ( ya¡1 ) = 1 a n d ya¡1 $ xi fo r s o m e i 2 [1 ; a ¡ 1 ]. If i = 1 ,
i.e ., x1 $ ya¡1. Th e n d( ya¡1 ) = 2 . N o w u s in g ( 1 ) a n d t h e fa c t t h a t d( u; fx0; x1g ) = 4 , we
o b t a in

d( u ) = d ( u; fx0; x1g ) + d¡ ( u; fx2; x3; : : : xa¡1g ) · a + 2 · 2 a ¡ 3 ;
wh ic h c o n t r a d ic t s c o n d it io n B0 s in c e fu; ya¡1g ! x1 a n d a ¸ 5 . Th e r e fo r e , i 2 [2 ; a ¡ 1 ].

A s s u m e , wit h o u t lo s s o f g e n e r a lit y, t h a t ya¡1 $ xa¡1. Th e n a( xi; ya¡1 ) = 0 fo r a ll
i 2 [1 ; a ¡ 2 ], in p a r t ic u la r , a ( x2; ya¡1 ) = a ( x3; ya¡1 ) = 0 . Th is t o g e t h e r wit h ( 1 ) im p lie s
t h a t maxfd( x2 ) ; d ( x3 ) g · 2 a ¡ 3 , wh ic h c o n t r a d ic t s c o n d it io n B0 s in c e fx2; x3g ! y1. Th e
d is c u s s io n o f S u b c a s e 2 .1 is c o m p le t e d .
Subcase 2.2: Y1 h a s e xa c t ly t wo ve r t ic e s o f d e g r e e le s s t h a n 2 a ¡ 2 .

A s s u m e , wit h o u t lo s s o f g e n e r a lit y, t h a t d( ya¡2 ) · 2 a ¡ 3 , d ( ya¡1 ) · 2 a ¡ 3 a n d d( yi ) ¸
2 a¡ 2 fo r a ll i 2 [1 ; a¡ 3 ]. Th e n it is e a s y t o s e e t h a t t h e s u b d ig r a p h DhX1 [Y1 nfya¡2; ya¡1gi
is a 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 X1 a n d Y1 n fya¡2; ya¡1g s in c e d( x0; Y1 ) = 0 .

Fo r t h e d is c u s s io n o f S u b c a s e 2 .2 it is c o n vie n t ¯ r s t t o p r o ve t h e fo llo win g Cla im s 1 a n d
2 b e lo w.
Claim 1: If xj ! ya¡2 fo r s o m e j 2 [2 ; a ¡ 1 ], t h e n d+ ( ya¡2; fx1; x2; : : : ; xa¡1g n fxjg ) = 0 .
P r oof of Claim 1: A s s u m e , wit h o u t lo s s o f g e n e r a lit y, t h a t xa¡1 ! ya¡2, i.e ., j = a ¡ 1 .
S u p p o s e t h a t t h e c la im is n o t t r u e , i.e ., ya¡2 ! xi fo r s o m e i 2 [1 ; a ¡ 2 ]. W e will c o n s id e r
t h e c a s e s i = 1 a n d i 2 [2 ; a ¡ 2 ] s e p a r a t e ly.

Case. i = 1 , i.e., ya¡2 ! x1.
Fir s t we s h o w t h a t

d+ ( u; fx2; x3; : : : ; xa¡1g ) = 0 : ( 2 )
P r oof of (2): S u p p o s e t h a t ( 2 ) is n o t t r u e , i.e ., t h e r e is a k 2 [2 ; a¡ 1 ] s u c h t h a t u ! xk.

If k 2 [2 ; a ¡ 2 ], we m a y a s s u m e , wit h o u t lo s s o f g e n e r a lit y, t h a t u ! x2. Th e n t h e c yc le
xa¡1ya¡2x1ux2y1x3y2 : : : xa¡2ya¡3xa¡1 is a c yc le o f le n g t h 2 a ¡ 2 , c o n t r a d ic t io n . A s s u m e
t h e r e fo r e t h a t k = a ¡ 1 . Th e n

u ! xa¡1 a n d d+ ( u; fx2; x3; : : : ; xa¡2g ) = 0 : ( 3 )



1 2 On pre-Hamiltonian Cycles in Balanced Bipartite Digraphs

If ya¡2 ! xl, fo r s o m e l 2 [2 ; a ¡ 2 ] ( s a y ya¡2 ! x2 ) , t h e n t h e c yc le
xa¡1ya¡2x2y1x3y2 : : : xa¡2ya¡3x1
uxa¡1 is a c yc le o f le n g t h 2 a ¡ 2 , a c o n t r a d ic t io n . A s s u m e t h e r e fo r e t h a t

d+ ( ya¡2; fx2; x3; : : : ; xa¡2g) = 0 : ( 4 )

If xl ! u fo r s o m e l 2 [2 ; a ¡ 2 ] ( s a y x2 ! u ) , t h e n t h e c yc le
xa¡1ya¡2x1y2x3y3 : : : ya¡3xa¡2y1x2uxa¡1 is a c yc le o f le n g t h 2 a ¡ 2 , a c o n t r a d ic t io n . A s s u m e
t h e r e fo r e t h a t

d¡ ( u; fx2; x3; : : : ; xa¡2g) = 0 :
Co m b in in g t h is t o g e t h e r wit h ( 3 ) a n d ( 4 ) , we o b t a in

d( u; fx2; x3; : : : ; xa¡2g ) = d+ ( ya¡2; fx2; x3; : : : ; xa¡2g ) = 0 :

Th e r e fo r e , s in c e a ¸ 5 , we h a ve d( x2 ) a n d d ( x3 ) · 2 a ¡ 3 , wh ic h c o n t r a d ic t s c o n d it io n B0
s in c e fx2; x3g ! y1. Th is c o n t r a d ic t io n p r o ve s ( 2 ) .

S in c e D is s t r o n g , fr o m ( 2 ) it fo llo ws t h a t u ! x1. Th e r e fo r e , fu; ya¡2g ! x1, i.e .,
fu; ya¡2g is a d o m in a t in g p a ir . Th is t o g e t h e r wit h c o n d it io n B0 im p lie s t h a t d( u ) ¸ 2 a ¡ 2
s in c e d ( ya¡2 ) · 2 a ¡ 3 ( b y o u r a s s u m p t io n ) . N o w u s in g ( 2 ) , we o b t a in

2 a ¡ 2 · d( u ) = d ( u; fx0; x1g ) + d¡ ( u; fx2; x3; : : : ; xa¡1g ) · 4 + a ¡ 2 = a + 2 :

H e n c e , a · 4 , wh ic h c o n t r a d ic t s t h a t a ¸ 5 . Th e d is c u s s io n o f t h e c a s e i = 1 is c o m p le t e d .

Case. i 2 [2 ; a ¡ 2 ], i.e., ya¡2 ! xi and ya¡2x1 =2 A ( D ) .
A s s u m e , wit h o u t lo s s o f g e n e r a lit y, t h a t ya¡2 ! x2, i.e ., i = 2 . N o w we p r o ve t h a t

d+ ( u; fx3; x4; : : : ; xa¡1g) = 0 : ( 5 )

P r oof of (5): S u p p o s e t h a t ( 5 ) is n o t t r u e , i.e ., t h e r e is a n l 2 [3 ; a ¡ 1 ] s u c h t h a t u ! xl.
If l = a ¡ 1 , i.e ., u ! xa¡1, t h e n t h e c yc le xa¡1ya¡2x2y2x3 : : : ya¡3xa¡2y1x1uxa¡1 is a c yc le
o f le n g t h 2 a ¡ 2 . A s s u m e t h e r e fo r e t h a t l 2 [3 ; a ¡ 2 ]. 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 u ! x3. Th e n t h e c yc le x1ux3y2x4 : : : ya¡4xa¡2ya¡3 xa¡1ya¡2x2y1x1 is a c yc le
o f le n g t h 2 a ¡ 2 . In b o t h c a s e s we h a ve a c yc le o f le n g t h 2 a ¡ 2 , wh ic h is a c o n t r a d ic t io n .
Th e r e fo r e , ( 5 ) is t r u e .

Fr o m ( 5 ) a n d 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 u ! x1 o r u ! x2.
A s s u m e ¯ r s t t h a t u ! x1. It is n o t d i± c u lt t o s h o w t h a t

d¡ ( u; fx2; x3; : : : ; xa¡2g) = 0 : ( 6 )

In d e e d , if x2 ! u, t h e n t h e c yc le ya¡2x2ux1y1x3y2x4 : : : xa¡2ya¡3xa¡1ya¡2 h a s le n g t h 2 a ¡ 2 ;
if xj ! u a n d j 2 [3 ; a ¡ 2 ], t h e n ( we m a y a s s u m e t h a t j = 3 , i.e ., x3 ! u ) t h e c yc le
xa¡1ya¡2x2y1x3ux1y2x4 : : : ya¡4xa¡2ya¡3xa¡1 h a s le n g t h 2 a ¡ 2 . In b o t h c a s e s 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 e qu a lit y ( 6 ) is t r u e .

If u ! x2, t h e n fr o m ya¡2 ! x2, d ( ya¡2 ) · 2 a ¡ 3 a n d c o n d it io n B0 it fo llo ws t h a t
d( u ) ¸ 2 a ¡ 2 . On t h e o t h e r h a n d , u s in g ( 5 ) a n d ( 6 ) we o b t a in

2 a ¡ 2 · d( u ) = d( u; fx0; x1g ) + d+ ( u; fx2; x3; : : : ; xa¡1g ) + d¡ ( u; fx2; x3; : : : ; xa¡1g ) · 6 :



S. Darbinyan 1 3

Th e r e fo r e , a · 4 , wh ic h c o n t r a d ic t s t h a t a ¸ 5 . A s s u m e t h e r e fo r e t h a t ux2 =2 A ( D ) . Th e n
b y ( 5 ) a n d ( 6 ) we h a ve

d+ ( u; fx2; x3; : : : ; xa¡1g ) = d¡ ( u; fx2; x3; : : : ; xa¡2g ) = 0 :

In p a r t ic u la r , a ( xj; u ) = 0 fo r a ll j 2 [2 ; a ¡ 2 ]. S in c e a ¸ 5 a n d s in c e fx2; x3g ! y1, it
fo llo ws t h a t d ( x2 ) = 2 a ¡ 2 o r d( x3 ) = 2 a ¡ 2 . If d ( x2 ) = 2 a ¡ 2 , t h e n fya¡2; ya¡1g ! x2, a n d
if d( x3 ) = 2 a ¡ 2 , t h e n fya¡2; ya¡1g ! x3. 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 t o c o n d it io n
B0.

A s s u m e s e c o n d t h a t ux1 =2 A( D ) a n d u ! x2. Th e n b y c o n d it io n B0 we h a ve d( u ) ¸ 2 a¡ 2
s in c e fu; ya¡2g ! x2 a n d d( ya¡2 ) · 2 a ¡ 3 . N o w u s in g ( 5 ) , we o b t a in

2 a ¡ 2 · d( u ) = d( u; fx0; x1g ) + d+ ( u; fx2; x3; : : : ; xa¡1g ) + d¡ ( u; fx2; x3; : : : ; xa¡1g ) · a + 2 ;

wh ic h is a c o n t r a d ic t io n , b e c a u s e o f a ¸ 5 . Cla im 1 is p r o ve d .
Claim 2: If xj ! ya¡2 fo r s o m e j 2 [2 ; a ¡ 1 ], t h e n d¡ ( ya¡2; fx2; x3; : : : ; xa¡1g n fxjg ) = 0 .
P r oof of Claim 2: A s s u m e , wit h o u t lo s s o f g e n e r a lit y, t h a t xa¡1 ! ya¡2, i.e ., j = a ¡ 1 .
S u p p o s e t h a t t h e c la im is n o t t r u e , i.e ., xl ! ya¡2 fo r s o m e l 2 [2 ; a ¡ 2 ]. Fr o m Cla im 1 a n d
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 ya¡2 ! xa¡1. Th is t o g e t h e r wit h c o n d it io n B0
a n d maxfd( ya¡2 ) ; d( ya¡1 ) g · 2 a ¡ 3 im p lie s t h a t ya¡1xa¡1 =2 A( D ) .

A s s u m e , wit h o u t lo s s o f g e n e r a lit y, t h a t x2 ! ya¡2, i.e ., l = 2 . If u ! x2, t h e n t h e
c yc le ya¡2xa¡1y2x3y3 : : : xa¡3ya¡3xa¡2y1x1ux2ya¡2 h a s le n g t h 2 a¡ 2 , wh ic h is a c o n t r a d ic t io n .
L e t u ! xk, wh e r e k 2 [3 ; a ¡ 2 ]. W e m a y a s s u m e t h a t k = 3 , i.e ., u ! x3. Th e n
ya¡2xa¡1y1x1ux3y2x4y3 : : : xa¡2ya¡3 x2ya¡2 is a c yc le o f le n g t h 2 a¡ 2 , wh ic h is a c o n t r a d ic t io n .
Th e r e fo r e , we m a y a s s u m e t h a t

d+ ( u; fx2; x3; : : : ; xa¡2g ) = 0 : ( 7 )

Fr o m ( 7 ) a n d 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 u ! x1 o r u ! xa¡1.
A s s u m e ¯ r s t t h a t u ! x1. It is n o t d i± c u lt t o s e e t h a t if fo r s o m e j 2 [3 ; a ¡ 2 ], s a y

j = 3 , xj ! u, t h e n t h e c yc le ya¡2xa¡1y1x3ux1y3x4 : : : ya¡3xa¡2y2x2ya¡2 h a s le n g t h 2 a2, a n d
if xa¡1 ! u, t h e n t h e c yc le ya¡2xa¡1ux1y1x3y3 : : : xa¡3ya¡3xa¡2y2x2ya¡2 h a s le n g t h 2 a ¡ 2 ,
wh ic h is a c o n t r a d ic t io n . A s s u m e t h e r e fo r e t h a t

d¡ ( u; fx3; x4; : : : ; xa¡1g ) = 0 : ( 8 )

N o w u s in g ( 7 ) a n d ( 8 ) , we o b t a in a( u; xj ) = 0 fo r a ll j 2 [3 ; a ¡ 2 ] a n d

d( u ) = d ( u; fx0; x1g ) + d+ ( u; fx2; x3; : : : ; xa¡1g ) + d¡ ( u; fx2; x3; : : : ; xa¡1g) · 6 · 2 a ¡ 3 :

Fr o m ( 7 ) , ( 8 ) a n d Cla im 1 it fo llo ws t h a t d ( xj ) · 2 a¡ 3 fo r a ll j 2 [3 ; a¡ 2 ]. H e n c e , a¡ 2 = 3 ,
i.e ., a = 5 a n d d ( x3 ) · 2 a ¡ 3 , a n d d ( x2 ) ; d( x4 ) ¸ 2 a ¡ 2 s in c e fx2; x3; : : : ; xa¡1g ! y1. Fr o m
ya¡1xa¡1 =2 A( D ) a n d xa¡1u =2 A( D ) ( a ¡ 1 = 4 ) it fo llo ws t h a t u ! xa¡1, wh ic h is a
c o n t r a d ic t io n s in c e fu; ya¡2g ! xa¡1 a n d maxfd ( u ) ; d ( ya¡2g · 2 a ¡ 3 .

A s s u m e s e c o n d t h a t u ! xa¡1 a n d ux1 =2 A( D ) . S in c e fu; ya¡2g ! xa¡1 a n d s in c e
d( ya¡2 ) · 2 a¡ 3 it fo llo ws t h a t d( u ) ¸ 2 a¡ 2 . On t h e o t h e r h a n d , u s in g ( 7 ) a n d ux1 =2 A ( D ) ,
we o b t a in

2 a ¡ 2 · d( u ) = d( u; fx0; x1g ) + d+ ( u; fx2; x3; : : : ; xa¡1g ) + d¡ ( u; fx2; x3; : : : ; xa¡1g ) · a + 2 ;



1 4 On pre-Hamiltonian Cycles in Balanced Bipartite Digraphs

wh ic h c o n t r a d ic t s t h a t a ¸ 5 . Cla im 2 is p r o ve d .

N o w we a r e r e a d y t o c o m p le t e t h e d is c u s s io n o f S u b c a s e 2 .2 .
A s s u m e t h a t d¡ ( yj; fx2; x3; : : : ; xa¡1g ) 6= 0 fo r j = a¡ 2 o r a¡ 1 ( s a y j = a ¡ 2 ) . A s s u m e ,

wit h o u t lo s s o f g e n e r a lit y, t h a t xa¡1 ! ya¡2. Fr o m Cla im s 1 a n d 2 it fo llo ws t h a t

d+ ( ya¡2; fx1; x2; x3; : : : ; xa¡2g ) = d¡ ( ya¡2; fx2; x3; : : : ; xa¡2g ) = 0 : ( 9 )

Th e r e fo r e , d( xi ) · 2 a ¡ 2 fo r a ll i 2 [2 ; a ¡ 2 ] s in c e a ( xi; ya¡2 ) = 0 . Fr o m s t r o n g ly c o n n e c t e d -
n e s s o f D a n d ( 9 ) it fo llo ws t h a t ya¡2 ! xa¡1. Th is t o g e t h e r wit h maxfd( ya¡2 ) ; d( ya¡1 ) g ·
2 a ¡ 3 a n d c o n d it io n B0 im p lie s t h a t ya¡1xa¡1 =2 A( D ) . Th e r e fo r e ,

d+ ( ya¡1; fx1; x2; x3; : : : ; xa¡2g ) 6= 0

s in c e D is s t r o n g . N o w we a p p ly Cla im 1 t o ya¡1 we c o n c lu d e t h a t xa¡1ya¡1 =2 A( D ) . Th e n
a( xa¡1; ya¡1 ) = 0 a n d d( xa¡1 ) · 2 a ¡ 2 . S in c e fx2; x3; : : : ; xa¡1g ! y1, fr o m c o n d it io n B0
it fo llo ws t h a t fx2; x3; : : : ; xa¡1g h a s a t le a s t a ¡ 3 ve r t ic e s o f d e g r e e a t le a s t 2 a ¡ 2 . In
p a r t ic u la r , d( x2 ) ¸ 2 a ¡ 2 o r d ( x3 ) ¸ 2 a ¡ 2 . W it h o u t lo s s o f g e n e r a lit y, we a s s u m e t h a t
d( x2 ) ¸ 2 a ¡ 2 . Th e n x2 ! fu; ya¡1g s in c e a( x2; ya¡2 ) = 0 . N o w u s in g ( 9 ) wit h r e s p e c t t o
ya¡1, we o b t a in

d+ ( ya¡1; fx1; x3; x4; : : : ; xa¡1g ) = d¡ ( ya¡1; fx3; x4; : : : ; xa¡1g ) = 0 : ( 1 0 )

In p a r t ic u la r , fr o m ( 9 ) a n d ( 1 0 ) we h a ve d¡ ( x1; fya¡2; ya¡1g ) = 0 . Th e r e fo r e , x1 ! ya¡2 a n d
u ! x1 s in c e d( x1 ) ¸ 2 a ¡ 2 . H e n c e , t h e c yc le x2ux1ya¡2xa¡1y1x3y2x4 : : : ya¡4xa¡2ya¡3x2 is
a c yc le o f le n g t h 2 a ¡ 2 , wh ic h is a c o n t r a d ic t io n .

A s s u m e n o w t h a t

A ( fx2; x3; : : : ; xa¡1g ! fya¡2; ya¡1g ) = 0 :

Th e n , s in c e D is s t r o n g , it fo llo ws t h a t x1 ! fya¡2; ya¡1g. Fr o m t h e la s t e qu a lit y we h a ve
d( xj ) · 2 a ¡ 2 fo r a ll j 2 [2 ; a ¡ 1 ]. Th is t o g e t h e r wit h fx2; x3; : : : ; xa¡1g ! y1 im p lie s t h a t
fx2; x3; : : : ; xa¡1g h a s a t le a s t a ¡ 3 ve r t ic e s o f d e g r e e e qu a l t o 2 a ¡ 2 . A s s u m e , wit h o u t lo s s
o f g e n e r a lit y, t h a t d ( x2 ) = 2 a ¡ 2 . Th e n fya¡2; ya¡1g ! x2, wh ic h is a c o n t r a d ic t io n s in c e
d( ya¡2 ) · 2 a ¡ 3 a n d d ( ya¡1 · 2 a ¡ 3 . In e a c h c a s e we o b t a in a c o n t r a d ic t io n , a n d h e n c e ,
t h e d is c u s s io n o f S u b c a s e 2 .2 is c o m p le t e d .
Subcase 2.3: Y1 h a s e xa c t ly t h r e e ve r t ic e s o f d e g r e e le s s t h a n 2 a ¡ 2 .

A s s u m e , wit h o u t lo s s o f g e n e r a lit y, t h a t d( yj ) · 2 a ¡ 3 fo r a ll j 2 [a ¡ 3 ; a ¡ 1 ] a n d
d( yi ) ¸ 2 a ¡ 2 fo r a ll i 2 [1 ; a ¡ 4 ]. Th e n it is e a s y t o s e e t h a t t h e s u b d ig r a p h DhfX1 [
fy1; y2; : : : ; ya¡4gi is a c o m p le t e b ip a r t it e d ig r a p h a n d d¡ ( xi; fya¡3; ya¡2; ya¡1g ) · 1 fo r a ll
i 2 [1 ; a ¡ 1 ]. Th is t o g e t h e r wit h c o n d it io n B0 im p lie s t h a t fx2; x3; : : : ; xa¡1g h a s a t le a s t
a ¡ 3 ve r t ic e s o f , s a y x2; x3; : : : ; xa¡2, o f d e g r e e e qu a l t o 2 a ¡ 2 . Th e n x1 $ u, xi !
fya¡3; ya¡2; ya¡1g if i 2 [1 ; a ¡ 2 ], a n d xj $ u if j 2 [2 ; a ¡ 2 ]. N o w it is n o t d i± c u lt t o s e e
t h a t fo r e ve r y i 2 [1 ; a ¡ 2 ] t h e r e is a j 2 [a ¡ 3 ; a ¡ 1 ] s u c h t h a t xi $ yj. B e c a u s e o f t h e
s ym m e t r y b e t we e n t h e ve r t ic e s x1; x2; : : : ; xa¡2, we c a n a s s u m e , x1 $ ya¡3.

A s s u m e ¯ r s t t h a t

A ( fya¡2; ya¡1g ! fx4; x5; : : : ; xa¡1g ) 6= ;:



S. Darbinyan 1 5

L e t ya¡2 ! xa¡1. Th e n t h e c yc le x2ux3ya¡3 x1ya¡2xa¡1y1x4y2 : : : xa¡2ya¡4x2 h a s le n g t h
2 a ¡ 2 , if a ¸ 6 , a n d t h e c yc le x2ux3y2x1y3x4y1x2, if a = 5 h a s le n g t h 2 a ¡ 2 , wh ic h is a
c o n t r a d ic t io n .

A s s u m e s e c o n d t h a t

A ( fya¡2; ya¡1g ! fx4; x5; : : : ; xa¡1g ) = ;:

Fr o m x1 $ ya¡3, maxfd ( ya¡3 ) ; d ( ya¡2 ) ; d( ya¡1 ) g · 2 a ¡ 3 a n d c o n d it io n B0 it fo llo ws t h a t

d¡ ( x1; fya¡2; ya¡3g ) = 0 a n d minfd+ ( ya¡2; fx2; x3g ) ; d+ ( ya¡1; fx2; x3gg ) ¸ 1 : ( 1 1 )

W it h o u t lo s s o f g e n e r a lit y, we a s s u m e t h a t ya¡2 ! x2. If a ¸ 6 , t h e n t h e c yc le
ya¡2x2ya¡3x1ux3y1xa¡1 y2x4y3 : : : xa¡3ya¡4xa¡2ya¡2 is a c yc le o f le n g t h 2 a ¡ 2 , wh ic h is
a c o n t r a d ic t io n . A s s u m e t h e r e fo r e t h a t a = 5 . N o w u s in g ( 1 1 ) , y3 ! x2, y2 ! x1
a n d c o n d it io n B0, we o b t a in y3 ! x3 a n d d+ ( y4; fx2; x3g ) = 0 . Th u s , we h a ve t h a t
Dhfx1; x2; x3; u; y1gi is a 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 fx1; x2; x3g a n d fu; y1g,
fx1; x2; x3g ! fy2; y3; y4g, x4 $ y1, xi $ yi+1 fo r a ll i 2 [1 ; 3 ] a n d x0 $ u. It is e a s y t o
c h e c k t h a t t h e o b t a in e d d ig r a p h is s t r o n g ly c o n n e c t e d a n d is o m o r p h ic t o D ( 1 0 ) , wh ic h s a t -
is ¯ e s c o n d it io n B0, b u t h a s n o c yc le o f le n g t h 8 . Th e t h e o r e m is p r o ve d .

Fr o m Th e o r e m s 1 .5 a n d 1 .6 fo llo ws t h e fo llo win g c o r o lla r y fo llo ws .
Cor ollar y: L et D be a strongly connected balanced bipartite digraph of order 2 a ¸ 1 0 . As-
sume that d ( x) +d( y ) ¸ 4 a¡ 3 for every dominaiting pair of vertices x and y. Then either the
underlying graph of D is 2-connected or D contains a cycle of length k for every k 2 [1 ; a¡ 1 ]
unless D is isomorphic to the digraph D ( 1 0 ) .

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 1 .

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

[3 ] C.S t .J.A . N a s h -W illia m s , \ H a m ilt o n c ir c u it s in g r a p h s a n d d ig r a p h s " , in The many
facets of graph theory, Springer Verlag L ecture Notes, vo l. 1 1 0 , p p . 2 3 7 -2 4 3 , 1 9 6 9 .

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

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

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

[7 ] M. Ovr e b e k-L a r is c h , \ A t h e o r e m o n p a n c yc lic o r ie n t e d g r a p h s " , J ournal of Combina-
torial Theory Ser. B , vo l. 2 1 , n o . 1 , p p . 7 6 -8 0 , 1 9 7 6 .

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

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



1 6 On pre-Hamiltonian Cycles in Balanced Bipartite Digraphs

[1 0 ] S .K h . D a r b in ya n , \ On p a n c yc lic d ig r a p h s " , P ereprint of the Computing Centre of the
Akademy Nauk Armyan. SSR 2 1 p p ., 1 9 7 9 .

[1 1 ] S .K h . D a r b in ya n , \ 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 " , Studia Scien-
tiarum M athematicarum Hungarica, vo l. 2 0 , n o . 1 -4 , p p . 9 5 -1 1 7 , 1 9 8 5 ( in R u s s ia n ) ( 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 e m y N a u k B S S R , Min s k, 1 9 8 1 ) .

[1 2 ] S .K h . D a r b in ya n , \ On t h e p a n c ylic 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 " , Akademy
Nauk Armyan. SSR D oklady, vo l. 8 3 , n o . 3 , p p . 9 9 -1 0 1 , 1 9 8 6 ( 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 ) .

[1 3 ] 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 0 , p p . 1 8 1 -1 8 7 , 1 9 9 6 .

[1 4 ] 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 . 6 1 -7 2 , 1 9 9 9 .

[1 5 ] J. A d a m u s , L . A d a m u s a n d A . Y e o , \ On t h e Me yn ie l c o n d it io n fo r h a m ilt o n ic it y in

b ip a r t it e d ig r a p h s " , D iscrete M ath.Theor. Comput. Sci., vo l. 1 6 , p p . 2 9 3 { 3 0 2 , 2 0 1 4 .
[1 6 ] R . W a n g , \ A s u ± c ie n t c o n d it io n fo r a b a la n c e d b ip a r t it e d ig r a p h t o b e h a m ilt o n ia n " ,

a r X Iv:1 5 0 6 .0 7 9 4 9 [m a t h . CO] 2 6 ju n 2 0 1 5 .
[1 7 ] S . K h . D a r b in ya n , \ S u ± c ie n t c o n d it io n s fo r h a m ilt o n ia n c yc le s in b ip a r t it e d ig r a p h s " ,

a r X iv: 1 6 0 4 .0 8 7 3 3 v1 [m a t h .CO] 2 9 A p r 2 0 1 6 .
[1 8 ] S .K h . D a r b in ya n , \ Cyc le s o f e a c h e ve n le n g t h s in b a la n c e d b ip a r t it e d ig r a p h s " , a r X iv:

1 6 0 4 .0 8 7 3 3 v1 [m a t h .CO] 1 4 Ju l 2 0 1 6 .

Submitted 14.06.2016, accepted 28.10.2016.

гí³ë³ñ³Ïßéí³Í »ñÏÙ³ë ÏáÕÙÝáñáßí³Í ·ñ³ýÝ»ñÇ
ݳ˳ѳÙÇÉïáÝÛ³Ý óÇÏÉ»ñÇ Ù³ëÇÝ

ê. ¸³ñµÇÝÛ³Ý

²Ù÷á÷áõÙ

гí³ë³ñ³Ïßéí³Í »ñÏÙ³ë ÏáÕÙÝáñáßí³Í ·ñ³ýÇ ÏáÕÙÝáñáßí³Í óÇÏÉÁ ÏáãíáõÙ ¿
ݳ˳ѳÙÇÉïáÝÛ³Ý, »Ã» ³ÛÝ å³ñáõݳÏáõÙ ¿ ³Û¹ ·ñ³ýÇ µáÉáñ ·³·³ÃÝ»ñÁ ` µ³óÇ
»ñÏáõëÇó:

Ü»ñϳ ³ß˳ï³ÝùáõÙ óáõÛó ¿ ïñíáõÙ Ñ»ï¨Û³É åݹáõÙÁ.
»áñ»Ù: ¸Çóáõù` D-Ý 2 a ¸ 1 0 ·³·³Ã³ÝÇ Ñ³í³ë³ñ³Ïßéí³Í »ñÏÙ³ë ÏáÕÙÝáñáßí³Í

·ñ³ý ¿: ºÃ» ³Û¹ ·ñ³ýÇ ·³·³ÃÝ»ñÇ ó³Ýϳó³Í ѳÕÃáÕ ½áõÛ·Ç ³éÝí³½Ý Ù»Ï ·³·³ÃÇ
ÉáÏ³É ³ëïÇ׳ÝÁ ÷áùñ ã¿ 2 a ¡ 2 ÃíÇó, ³å³ D-Ý å³ñáõݳÏáõÙ ¿ ݳ˳ѳÙÇÉïáÝÛ³Ý 

óÇÏÉ Ï³Ù D-Ç ãÏáÕÙÝáñáßí³Í ÑÇÙù ·ñ³ýÁ 2 -ϳå³Ïóí³Í ¿ ϳ٠D-Ý Ç½áÙáñý ¿ Ù»Ï 10
·³·³Ã³ÝÇ ·ñ³ýÇÝ:



S. Darbinyan 1 7

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

Ñ. Äàðáèíÿí

Àííîòàöèÿ

Îðèåíòèðîâàííûé êîíòóð ïðîõîäÿùèé ÷åðåç âñå âåðøèíû ñáàëàíñèðîâàííîãî
äâóäîëüíîãî îðãðàôà, êðîìå äâóõ âåðøèí, íàçûâàåòñÿ ïðåäãàìèëüòîíîâûì
êîíòóðîì. Â íàñòîÿùåé ñòàòüå äîêàçûâàåòñÿ:

Òåîðåìà: Ïóñòü D - 2 a-âåðøèííûé ( a ¸ 5 ) ñáàëàíñèðîâàííûé äâóäîëüíûé
îðãðàô. Åñëè äëÿ ëþáûõ äîìèíèðóþùèõ ïàð âåðøèí ïî êðàéíåé ìåðå îäíà
âåðøèíà èìååò ëîêàëüíóþ ñòåïåíü íå ìåíüøå ÷åì 2 a ¡ 2 , òî D ñîäåðæèò
ïðåäãàìèëüòîíîâûé êîíòóð èëè íåîðèåíòèðîâàííàÿ îñíîâà ãðàô îðãðàôà
ÿâëÿåòñÿ D 2-ñâÿçíîé èëè D èçîìîðôåí îäíîìó îðãðàôó ñ äåñÿòüþ âåðøèíàìè.