D:\User\...\main.DVI


Mathematical Problems of Computer Science 49, 26{34, 2018.

On a P r oblem of Wang Concer ning the H amiltonicity

of B ipar tite 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: amdarbin@ipia.sci.am, isko@ipia.sci.am

Abstract

R. Wang (Discrete Mathematics and Theoretical Computer Science, vol. 19(3),
2017) proposed the following problem.

Problem. Let D be a strongly connected balanced bipartite directed graph of
order 2a ¸ 8. Suppose that d(x) ¸ 2a ¡ k, d(y) ¸ a + k or d(y) ¸ 2a ¡ k, d(x) ¸ a + k
for every pair of vertices fx; yg with a common out-neighbour, where 2 · k · a=2. Is
D Hamiltonian?

In this paper, we prove that if a digraph D satis¯es the conditions of this problem,
then

(i) D contains a cycle factor,
(ii) for every vertex x 2 V (D) there exists a vertex y 2 V (D) such that x and y

have a common out-neighbour.
Keywords: Digraph, cycle, Hamiltonian cycle, Bipartite balanced digraph, Perfect

matching.

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

In t h is p a p e r , we c o n s id e r ¯ n it e d ir e c t e d g r a p h s ( 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 .
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 H a m ilt o n ia n c yc le , i.e ., a c yc le t h a t in c lu d e s
e ve r y ve r t e x o f D. Th e ve r t e x s e t a n d t h e a r c s e t o f a d ig r a p h D a r e d e n o t e d b y V ( D ) a n d
A( D ) , r e s p e c t ive ly. Th e o r d e r o f a d ig r a p h D is t h e n u m b e r o f it s ve r t ic e s . A c yc le fa c t o r in D
is a c o lle c t io n o f ve r t e x-d is jo in t c yc le s C1; C2; : : : ; Cl s u c h t h a t V ( C1 ) [V ( C2 ) [: : :[V ( Cl ) =
V ( D ) . A d ig r a p h D is 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 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.

Th e r e a r e a n u m b e r o f c o n d it io n s t h a t g u a r a n t e e t h a t a b ip a r t it e d ig r a p h is H a m ilt o n ia n
( s e e , e .g ., [1 ]-[1 1 ]) . L e t u s r e c a ll t h e fo llo win g d e g r e e c o n d it io n s t h a t g u a r a n t e e t h a t a b a l-
a n c e d b ip a r t it e d ig r a p h is H a m ilt o n ia n .

T heor em 1.1. ( A d a m u s , A d a m u s a n d Y e o [8 ]) L et D be a balanced bipartite digraph of
order 2 a, where a ¸ 2 . Then D is Hamiltonian provided one of the following holds:

(a) d ( u) + d ( v ) ¸ 3 a + 1 for every pair of non-adjacent distinct vertices u and v of D;
(b) D is strongly connected and d( u ) + d( v ) ¸ 3 a for every pair of non-adjacent distinct

vertices u and v of D;

2 6



S. Darbinyan and I. Karapetyan 2 7

(c) the minimal degree of D is at least ( 3 a + 1 ) = 2 ;
(d) D is strongly connected, and the minimal degree of D is at least 3 a=2 .

Ob s e r ve t h a t Th e o r e m 1 .1 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 .
In t h e fo llo win g t h e o r e m s a d e g r e e c o n d it io n r e qu ir e s o n ly fo r s o m e p a ir s o f n o n -a d ja c e n t
ve r t ic e s .

T heor em 1.2. ( J. A d a m u s [9 ]) L et D be a strongly connected balanced bipartite digraph of
order 2 a ¸ 6 . If d( x ) +d( y ) ¸ 3 a for every pair of vertices x, y with a common out-neighbour
or a common in-neighbour, then D is Hamiltonian.

N o t ic e t h a t Th e o r e m 1 .2 im p r o ve s Th e o r e m 1 .1 .

S o m e s u ± c ie n t c o n d it io n s fo r t h e e xis t e n c e o f H a m ilt o n ia n c yc le s in a b ip a r t it e t o u r n a -
m e n t a r e d e s c r ib e d in t h e s u r ve y p a p e r [3 ] b y Gu t in . A c h a r a c t e r iz a t io n fo r h a m ilt o n ic it y
fo r s e m ic o m p le t e b ip a r t it e d ig r a p h s wa s o b t a in e d in d e p e n d e n t ly b y Gu t in [2 ] a n d H Äa g g kvis t
a n d Ma n o u s s a kis [4 ].

T heor em 1.3. ( W a n g [1 0 ]) L et D be a strongly connected balanced bipartite digraph of
order 2 a, where a ¸ 1 . Suppose that, for every pair of vertices fx; yg with a common out-
neighbour, 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.

B e fo r e s t a t in g t h e n e xt t h e o r e m we n e e d t o d e ¯ n 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
e ig h t .

E xample 1. 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, a n d t h e a r c s e t A ( D ( 8 ) ) c o n t a in s e xa c t ly t h e fo llo win g a r c s : y0x1, y1x0,
x2y3, x3y2 a n d a ll t h e a r c s o f t h e fo llo win g 2 -c yc le s : xi $ yi, i 2 [0 ; 3 ], y0 $ x2, y0 $ x3,
y1 $ x2 a n d y1 $ x3.

It is e a s y t o s e e t h a t

d( x2 ) = d( x3 ) = d ( y0 ) = d( y1 ) = 7 a n d d( x0 ) = d( x1 ) = d ( y2 ) = d( y3 ) = 3 ;

a n d t h e d o m in a t in g p a ir s in D ( 8 ) a r e : fy0; y1g, fy0; y2g,fy0; y3g,fy1; y2g, fy1; y3g, fx0; x2g,
fx0; x3g, fx1; x2g, fx1; x3g a n d fx2; x3g. N o t e t h a t e ve r y d o m in a t in g p a ir s a t is ¯ e s t h e c o n -
d it io n B1. S in c e x0y0x3y2x2 y1x0 is a c yc le in D ( 8 ) , it is n o t d i± c u lt t o c h e c k t h a t D ( 8 ) is
s t r o n g .

Ob s e r ve t h a t D ( 8 ) is n o t H a m ilt o n ia n . In d e e d , if C is a H a m ilt o n ia n c yc le in D ( 8 ) , t h e n
C wo u ld c o n t a in t h e a r c s x1y1 a n d x0y0. Th e r e fo r e , C wo u ld c o n t a in t h e p a t h x1y1x0y0 o r
t h e p a t h x0y0x1y1, wh ic h is im p o s s ib le s in c e N

¡ ( x0 ) = N
¡ ( x1 ) = fy0; y1g.

N o t ic e t h a t t h e d ig r a p h D ( 8 ) d o e s n o t s a t is fy t h e c o n d it io n s o f W a n g 's t h e o r e m .

T heor em 1.4. ( D a r b in ya n [1 1 ]) L et D be a strongly connected balanced bipartite digraph of
order 2 a ¸ 8 . Suppose that maxfd( x ) ; d( y ) g ¸ 2 a ¡ 1 for every pair of vertices x, y with a
common out-neighbour. Then D is Hamiltonian unless D is isomorphic to the digraph D ( 8 )
(for de¯nition of D ( 8 ) , see E xample 1).



2 8 On a Problem of Wang Concerning the Hamiltonicity of Bipartite Digraphs

Fo r a ¸ 4 Th e o r e m 1 .4 im p r o ve s W a n g 's t h e o r e m .

A d ig r a p h D is c a lle 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 · jV ( D ) j. 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 is e ve n 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
2 k, 2 · k · a.

Th e r e a r e va r io u s s u ± c ie n t c o n d it io n s fo r a d ig r a p h ( u n d ir e c t e d g r a p h ) t o b e H a m ilt o -
n ia n , t h e y a r e a ls o s u ± c ie n t fo r t h e d ig r a p h ( u n d ir e c t e d g r a p h ) t o b e p a n c yc lic .

R e c e n t ly, t h e fo llo win g r e s u lt s we r e p r o ve d .

T heor em 1.5. ( D a r b in ya n [1 2 ]) L et D be a strongly connected balanced bipartite digraph of
order 2 a ¸ 8 other than a directed cycle of length 2 a. If 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 the digraph D ( 8 ) .

T heor em 1.6. ( Me s z ka [1 3 ]) L et D be a balanced bipartite digraph of order 2 a ¸ 4 with
partite sets X and Y . If d ( x) + d ( y ) ¸ 3 a + 1 for every pair of distinct vertices fx; yg ei-
ther both in X or both in Y , then D contains cycles of all even lengths less than or equal to 2 a.

T heor em 1.7. ( D a r b in ya n [1 4 ]) L et D be a strongly connected balanced bipartite digraph
of order 2 a ¸ 6 with partite sets X and Y . If d( x ) + d( y ) ¸ 3 a for every pair of distinct
vertices fx; yg either both in X or both in Y , then D contains cycles of all even lengths less
than or equal to 2 a.

T heor em 1.8. ( A d a m u s [1 5 ]) L et D be a strongly connected balanced bipartite digraph of
order 2 a ¸ 6 . If d ( x) + d( y ) ¸ 3 a for every pair of distinct vertices fx; yg with a common
in-neighbour or a common out-neighbour, then D contains cycles of all even lengths less than
or equal to 2 a or a directed cycle of length 2 a.

De¯nition 1. L et D be a balanced bipartite digraph of order 2 a, where a ¸ 2 . F or any
integer k ¸ 0 , we will say that D satis¯es the condition Bk when

d( x ) ¸ 2 a ¡ k; d( y ) ¸ a + k or d( x ) ¸ a + k; d( y ) ¸ 2 a ¡ k

for any dominating pair of vertices fx; yg in D.

In [1 0 ], W a n g p r o p o s e d t h e fo llo win g p r o b le m .

P r oblem ( W a n g [1 0 ]) . L et D be a strongly connected balanced bipartite digraph of order
2 a ¸ 8 satisfying the condition Bk with 2 · k · a= 2 . Is D Hamiltonian?

B e fo r e s t a t in g t h e n e xt t h e o r e m s we n e e d t o d e ¯ n e a d ig r a p h o f o r d e r t e n .

E xample 2. 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 : Th e in d u c e d s u b d ig r a p h
hfx1; x2; x3; y0; y4gi 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; y4g;
fx1; x2; x3g ! fy1; y2; y3g; x4 $ y4; x0 $ y0, x3 $ y1 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 .



S. Darbinyan and I. Karapetyan 2 9

It is e a s y 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 t h e c o n d i-
t io n B0, b u t t h e u n d e r lyin g u n d ir e c t e d 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 ) . S in c e x1y1x3y3x2y2x1 is a c yc le o f le n g t h 6 , x0 $ y0 a n d x4 $ y4, it is n o t d i± c u lt
t o c h e c k t h a t a n y d ig r a p h o b t a in e d fr o m D ( 1 0 ) b y a d d in g a n e w a r c t h e o n e e n d -ve r t e x o f
wh ic h is x0 o r x4 c o n t a in s a c yc le o f le n g t h e ig h t . Mo r e o ve r , if t o A( D ) we a d d s o m e n e w
a r c s o f t h e t yp e yixj , wh e r e i 2 [1 ; 3 ] a n d j 2 [1 ; 3 ], t h e n we a lwa ys o b t a in a d ig r a p h , wh ic h
d o e s n o t s a t is fy t h e c o n d it io n B0.

T heor em 1.9. ( [1 6 ], [1 7 ]) . L et D be a balanced bipartite digraph of order 2 a ¸ 1 0
other than a directed cycle of length 2 a. Suppose that D satis¯es the condition B0, i.e.,
maxfd( x ) ; d( y ) g ¸ 2 a ¡ 2 for every dominating pair of vertices fx; yg. Then D contains
cycles of all lengths 2 ; 4 ; : : : ; 2 a ¡ 2 unless D is isomorphic to the digraph D ( 1 0 ) .

Cle a r ly, t h e e xis t e n c e o f a c yc le fa c t o r is a n e c e s s a r y 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 . In t h is n o t e we p r o ve t h e fo llo win g t h e o r e m .

T heor em 1.10. L et D be a strongly connected balanced bipartite digraph of order 2 a ¸ 8
satisfying the condition Bk with 2 · k · a= 2 . Then D contains a cycle factor.

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

Te r m in o lo g y a n d n o t a t io n n o t d e s c r ib e d b e lo w fo llo w [1 ]. If xy 2 A ( D ) , t h e n we s a y t h a t x
d o m in a t e s y o r y is a n o u t -n e ig h b o u r o f x a n d x is a n in -n e ig h b o u r o f y.

L e t x; y b e d is t in c t ve r t ic e s in a d ig r a p h D. Th e p a ir fx; yg is c a lle d 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 xz 2 A( D ) a n d yz 2 A ( D ) . In t h is c a s e we s a y t h a t x is a
p a r t n e r o f y a n d y is a p a r t n e r o f x. If x 2 V ( D ) a n d A = fxg we s o m e t im e s will wr it e
x in s t e a d o f fxg. A ! B m e a n s 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. Th e
n o t a t io n x $ y d e n o t e s t h a t xy 2 A ( D ) a n d yx 2 A ( D ) .

L e t N + ( x ) , N¡ ( x) d e n o t e t h e s e t o f o u t -n e ig h b o u r s , r e s p e c t ive ly t h e s e t o f in -n e ig h b o u r s
o f a ve r t e x x in a d ig r a p h D. If A µ V ( D ) , t h e n N + ( x; A ) = A \ N + ( x ) , N¡ ( x; A ) =
A\N ¡ ( x ) a n d N + ( A) = [x2AN + ( x) , N¡ ( A) = [x2AN¡ ( x) . Th e o u t -d e g r e e o f x is d+ ( x ) =
jN + ( x) j a n d d¡ ( x ) = jN¡ ( x) j is t h e in -d e g r e e o f x. S im ila r ly, d+ ( x; A) = jN + ( x; A) j a n d
d¡ ( x; A ) = jN¡ ( x; A ) j. Th e d e g r e e o f t h e ve r t e x x in D is d e ¯ n e d a s d( x ) = d+ ( x ) + d¡ ( x )
( s im ila r ly, d( x; A) = d+ ( x; A ) + d¡ ( x; A ) ) .

Th e p a t h ( r e s p e c t ive ly, t h e c yc le ) c o n s is t in g o f t h e d is t in c t ve r t ic e s x1; x2; : : : ; xm ( m ¸
2 ) a n d t h e a r c s xixi+1, i 2 [1 ; m ¡ 1 ] ( r e s p e c t ive ly, xixi+1, i 2 [1 ; m ¡ 1 ], a n d xmx1 ) , is
d e n o t e d b y x1x2 ¢ ¢ ¢ xm ( r e s p e c t ive ly, 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 . Give n a ve r t e x x o f a d ir e c t e d p a t h P o r a d ir e c t e d c yc le
C, we d e n o t e b y x+ ( r e s p e c t ive ly, b y x¡ ) t h e s u c c e s s o r ( r e s p e c t ive ly, t h e p r e d e c e s s o r ) o f x
( o n P o r C ) , a n d in c a s e o f a m b ig u it y, we p r e c is e P o r C a s a s u b s c r ip t ( t h a t is x+P . . . ) .

A 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 n ( x; y ) -p a t h in D fo r
e ve r y o r d e r e d p a ir o f d is t in c t ve r t ic e s x; y o f D. Two d is t in c t ve r t ic e s x a n d y a r e a d ja c e n t
if xy 2 A( D ) o r yx 2 A ( D ) ( o r b o t h ) .

L e t H b e a n o n -t r ivia l p r o p e r s u b s e t o f ve r t ic e s o f a d ig r a p h D. A n ( x; y ) -p a t h P is a n
H-b yp a s s if jV ( P ) j ¸ 3 , x 6= y a n d V ( P ) \ H = fx; yg.



3 0 On a Problem of Wang Concerning the Hamiltonicity of Bipartite Digraphs

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 wit h p a r t it e s e t s X a n d Y . A m a t c h in g fr o m X t o
Y is a n in d e p e n d e n t s e t o f a r c s wit h o r ig in in X a n d t e r m in u s in Y . ( A s e t o f a r c s wit h n o
c o m m o n e n d -ve r t ic e s is c a lle d in d e p e n d e n t ) . If D is b a la n c e d , o n e s a ys t h a t s u c h a m a t c h in g
is p e r fe c t if it c o n s is t s o f p r e c is e ly jXj a r c s .
Th e u n d e r lyin g u n d ir e c t e d g r a p h o f a d ig r a p h D is d e n o t e d b y UG( D ) , it c o n t a in s a n e d g e
xy if xy 2 A ( D ) o r yx 2 A( D ) ( o r b o t h ) .

3 . Ma in R e s u lt

Th e o r e m 1 .1 0 is t h e m a in r e s u lt o f t h is p a p e r .

P r oof of theor em 1.10. L e t D b e a d ig r a p h s a t is fyin g t h e c o n d it io n s o f t h e t h e o r e m . Or e
in [1 8 ] ( S e c t io n 8 .6 ) h a s s h o wn t h a t a b a la n c e d b ip a r t it e d ig r a p h D wit h p a r t it e s e t s X a n d
Y h a s a c yc le fa c t o r if a n d o n ly if D c o n t a in s a p e r fe c t m a t c h in g fr o m X t o Y a n d a p e r fe c t
m a t c h in g fr o m Y t o X.

Th e r e fo r e , b y t h e we ll-kn o wn K Äo n in g -H a ll t h e o r e m ( s e e , e .g ., [1 9 ]) t o s h o w t h a t D c o n -
t a in s a p e r fe c t m a t c h in g fr o m X t o Y , it s u ± c e s t o s h o w t h a t jN + ( S ) j ¸ jSj fo r e ve r y s e t
S µ X. L e t S µ X. If jSj = 1 o r jSj = a, t h e n jN + ( S ) j ¸ jSj s in c e D is s t r o n g ly c o n n e c t e d .
A s s u m e t h a t 2 · jSj · a ¡ 1 . W e c la im t h a t jN + ( S ) j ¸ jSj. 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 , i.e ., jN + ( S ) j · jSj ¡ 1 · a ¡ 2 . Fr o m t h is 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 t h e r e a r e t wo ve r t ic e s x; y 2 S a n d a ve r t e x z 2 N + ( S ) s u c h t h a t fx; yg ! z, i.e .,
fx; yg is a d o m in a t in g p a ir . Th e r e fo r e , b y c o n d it io n Bk, d ( x) ¸ 2 a ¡ k a n d d ( y ) ¸ a + k o r
d( x ) ¸ a + k a n d d( y ) ¸ 2 a ¡ k. 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 ¡ k
a n d d( y ) ¸ a + k. Th e n

2 a ¡ k · d ( x) · 2 jN + ( S ) j + a ¡ jN + ( S ) j = a + jN + ( S ) j:

Th e r e fo r e , jN + ( S ) j ¸ a ¡ k a n d jSj ¸ a ¡ k + 1 .
P r oposition 1. L e t fu; vg b e a d o m in a t in g p a ir o f ve r t ic e s o f D. Th e n fr o m c o n d it io n Bk
a n d 2 · k · a=2 it fo llo ws t h a t d( u ) ¸ a + k a n d d( vu ) ¸ a + k, i.e ., if a ve r t e x z h a s a
p a r t n e r in D , t h e n d ( z ) ¸ a + k.

W e c la im t h a t e a c h ve r t e x in Y nN + ( S ) h a s n o p a r t n e r in D. In d e e d , le t u b e a n a r b it r a r y
ve r t e x in Y n N + ( S ) . S in c e jSj ¸ a ¡ k + 1 , we h a ve

d( u ) · jSj + 2 ( a ¡ jSj ) = 2 a ¡ jSj · a + k ¡ 1 ;

wh ic h c o n t r a d ic t s P r o p o s it io n 1 . Th is m e a n s t h a t u h a s n o p a r t n e r in D.

W it h o u t lo s s o f g e n e r a lit y, a s s u m e t h a t

S = fx1; x2; : : : ; xsg a n d N + ( S ) = fy1; y2; : : : ; ytg:

R e c a ll t h a t e ve r y ve r t e x yi wit h t+1 · i · a h a s n o p a r t n e r in D. N o t e t h a t s ¸ t+1 , a¡s ·
a¡t¡ 1 a n d t h e r e is n o a r c fr o m a ve r t e x o f fx1; x2; : : : ; xsg t o a ve r t e x o f fyt+1; yt+2; : : : ; yag.
Fr o m t h is 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 t h e r e is a ve r t e x xi1 s u c h t h a t
yt+1xi1 2 A( D ) . S in c e yt+1 h a s n o p a r t n e r , it fo llo ws t h a t d¡ ( xi1; Y nfyt+1g ) = 0 . Th e r e fo r e ,
d( xi1 ) · a + 1 · a + k ¡ 1 s in c e k ¸ 2 . B y P r o p o s it io n 1 , t h is m e a n s t h a t t h e ve r t e x



S. Darbinyan and I. Karapetyan 3 1

xi1 a ls o h a s n o p a r t n e r . S in c e D is s t r o n g ly c o n n e c t e d , t h e r e is a ve r t e x yi2 2 Y s u c h
t h a t xi1yi2 2 A ( D ) . Th e n d¡ ( yi2; X n fxi1g ) = 0 , b e c a u s e o f t h e fa c t t h a t xi1 h a s n o
p a r t n e r . Th e r e fo r e , d( yi2 ) · a + 1 a n d h e n c e , yi2 a ls o h a s n o p a r t n e r . Co n t in u in g t h is
p r o c e s s , a s lo n g a s p o s s ib le , a s a r e s u lt we o b t a in a p a t h P = yt+1xi1yi2 xi2 : : : xil yil o r a c yc le
C = yt+1xi1yi2xi2 : : : xil yt+1. It is n o t d i± c u lt t o s e e t h a t a ll t h e ve r t ic e s o f t h is p a t h ( c yc le )
h a ve n o p a r t n e r s . If t h e fo r m e r c a s e h o ld s , t h e n x1 is in P , wh ic h is a c o n t r a d ic t io n s in c e x1
h a s a p a r t n e r ( n a m e ly x2 ) .

If t h e s e c o n d c a s e h o ld s , t h e n , s in c e e ve r y ve r t e x o f C h a s n o p a r t n e r in D, it fo llo ws t h a t
t h e r e is n o a r c fr o m a ve r t e x o f V ( D ) n V ( C ) t o a ve r t e x o f V ( C ) , wh ic h c o n t r a d ic t s t h a t
D is s t r o n g ly c o n n e c t e d . Th is c o m p le t e s t h e p r o o f o f t h e e xis t e n c e o f a p e r fe c t m a t c h in g
fr o m X t o Y . Th e p r o o f fo r a p e r fe c t m a t c h in g in t h e o p p o s it e d ir e c t io n is a n a lo g o u s . Th is
c o m p le t e s t h e p r o o f o f t h e t h e o r e m .

4 . R e m a r ks

N o w u s in g Th e o r e m 1 .1 0 , we p r o ve t h e fo llo win g r e s u lt s ( L e m m a s 3 .1 -3 .3 ) .

Lemma 3.1. L et D be a strongly connected balanced bipartite digraph of order 2 a ¸ 8 with
partite sets X and Y satisfying the condition Bk, 2 · k · a= 2 . If D is not Hamiltonian,
then every vertex u 2 V ( D ) has a partner in D.
P r oof of Lemma 3.1: L e t D b e a d ig r a p h s a t is fyin g t h e c o n d it io n s o f t h e le m m a . Fo r a
p r o o f b y c o n t r a d ic t io n , s u p p o s e t h a t t h e r e is a ve r t e x x in D, wh ic h h a s n o p a r t n e r . B y
Th e o r e m 1 .1 0 , D h a s a c yc le fa c t o r , s a y C1, C2, ... , Cl. Th e n l ¸ 2 s in c e D is n o t H a m il-
t o n ia n . 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 x 2 V ( C1 ) . It fo llo ws t h a t d¡ ( x+C1 ) = 1 .
Th e r e fo r e , d( x+C1 ) · a + 1 . B y P r o p o s it io n 1 , t h is m e a n s t h a t t h e ve r t e x x

+
C1

a ls o h a s n o
p a r t n e r . S im ila r ly, we o b t a in t h a t d( x++C1 ) · a + 1 ( wh e r e x

++
C1

d e n o t e s t h e s u c c e s s o r o f x+C1
o n C1 ) a n d h e n c e , x

++
C1

a ls o h a s n o p a r t n e r in D. Co n t in u in g t h is p r o c e s s , we c o n c lu d e t h a t
e ve r y ve r t e x o f C1 h a s n o p a r t n e r in D. Th is im p lie s t h a t t h e r e is n o a r c fr o m a ve r t e x o f
A ( V ( D ) n V ( C1 ) t o a ve r t e x o f V ( C1 ) ) , wh ic h c o n t r a d ic t s t h a t D is s t r o n g ly c o n n e c t e d . Th e
le m m a is p r o ve d .

Lemma 3.2. L et D be a strongly connected balanced bipartite digraph of order 2 a ¸ 8 with
partite sets X and Y satisfying the condition Bk, 2 · k · a=2 . If D is not a cycle, then D
contains a non-Hamiltonian cycle of length at least four.

P r oof of Lemma 3.2: L e t D b e a d ig r a p h s a t is fyin g t h e c o n d it io n s o f t h e le m m a . Fo r a
p r o o f b y c o n t r a d ic t io n , s u p p o s e t h a t D c o n t a in s a n o n -H a m ilt o n ia n c yc le o f le n g t h a t le a s t
fo u r .

If D is H a m ilt o n ia n , t h e n it is n o t d i± c u lt t o s h o w t h a t D c o n t a in s a n o n -H a m ilt o n ia n
c yc le o f le n g t h a t le a s t 4 . S o we s u p p o s e , fr o m n o w o n , t h a t D is n o t H a m ilt o n ia n a n d
c o n t a in s n o c yc le o f le n g t h a t le a s t 4 . B y Th e o r e m 1 .1 0 , D c o n t a in s a c yc le fa c t o r . L e t
C1; C2; : : : ; Ct b e a m in im a l c yc le fa c t o r o f D ( i.e ., t is a s s m a ll a s p o s s ib le ) . Th e n t h e le n g t h
o f e ve r y Ci is e qu a l t o t wo a n d t = a. L e t Ci = xiyixi, wh e r e xi 2 X a n d yi 2 Y . B y
L e m m a 3 .1 , e ve r y ve r t e x o f D h a s a p a r t n e r . Th is m e a n s t h a t fo r e ve r y ve r t e x x 2 V ( D ) ,
d( x ) ¸ a + k a n d d¡ ( x) ¸ k ¸ 2 , d+ ( x ) ¸ k ¸ 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
fx1; xjg wit h j 6= 1 is a d o m in a t in g p a ir a n d d( x1 ) ¸ 2 a ¡ k.



3 2 On a Problem of Wang Concerning the Hamiltonicity of Bipartite Digraphs

L e t Z b e t h e s u b s e t o f Y wit h t h e m a xim u m c a r d in a lit y, s u c h t h a t e ve r y ve r t e x o f Z
t o g e t h e r wit h x1 fo r m s a c yc le o f le n g t h t wo . 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
Z = fy1; y2; : : : ; ylg. Th e n 2 a ¡ k · d ( x1 ) · 2 l + a ¡ l = a + l. H e n c e , l ¸ a ¡ k. S in c e
D c o n t a in s n o c yc le o f le n g t h fo u r , it fo llo ws t h a t t h e ve r t ic e s y1 a n d xi, 2 · i · l, a r e n o t
a d ja c e n t . Th e r e fo r e ,

a + k · d( y1 ) · 2 a ¡ 2 l + 2 · 2 k + 2 ;
i.e ., k ¸ a ¡ 2 . S in c e a= 2 ¸ k ¸ a ¡ 2 , we h a ve a ¸ 2 k ¸ 2 a ¡ 4 , a · 4 . If a = 4 , t h e n
k = a=2 = 2 a n d l = a ¡ k = 2 . It is e a s y t o s e e t h a t d ( x1 ) = d ( y1 ) = 6 , t h e ve r t ic e s y1 a n d
xi, 3 · i · 4 , fo r m a c yc le o f le n g t h t wo a n d x1y3 2 A ( D ) o r y3x1 2 A ( D ) . N o w it e a s y t o
s e e t h a t D c o n t a in s a c yc le o f le n g t h fo u r . L e m m a 3 .2 is p r o ve d .

Fo r t h e n e xt le m m a we n e e d t h e fo llo win g le m m a d u e t o B o n d y.

B ypass Lemma ( L e m m a 3 .1 7 , B o n d y [2 0 ]) . L et D be a strong non-separable (i.e., UG ( D )
is 2-connected) digraph, and let H be a non-trivial proper subdigraph of D. Then D contains
an H-bypass.

Remar k: On e c a n p r o ve B yp a s s L e m m a u s in g t h e p r o o f o f Th e o r e m 5 .4 .2 [1 ].

N o w we will p r o ve t h e fo llo win g le m m a .

Lemma 3.3. L et D be a strongly connected balanced bipartite digraph of order 2 a ¸ 8 with
partite sets X and Y satisfying the condition Bk, where 2 · k · a=2 . Then the following
statements hold:

(i) the underlying undirected graph UG ( D ) is 2-connected;
(ii) if C is a cycle of length m, 2 · m · 2 a ¡ 2 , then D contains a C-bypass.

P r oof of Lemma 3.3. ( i) 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 is a s t r o n g ly c o n n e c t e d 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 ¸ 8 wit h p a r t it e s e t s X a n d Y s a t is ¯ e s t h e c o n d it io n Bk b u t
UG ( D ) is n o t 2 -c o n n e c t e d . Th e n V ( D ) = E [ F [ fug, wh e r e E a n d F a r e n o n -e m p t y
s u b s e t s , E \ F = ;, u =2 E [ F a n d t h e r e is n o a r c b e t we e n E a n d F . S in c e D is s t r o n g ,
it fo llo ws t h a t t h e r e a r e ve r t ic e s x 2 E a n d y 2 F s u c h t h a t fx; yg ! u, i.e ., fx; yg is a
d o m in a t in g p a ir . 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 x; y 2 X. Th e n u 2 Y . B y
c o n d it io n Bk, it is e a s y t o s e e t h a t

3 a · d( x ) + d( y ) · 4 + 2 jE \ Y j + 2 jF \ Y j · 2 a + 2 ;

wh ic h is a c o n t r a d ic t io n . Th is p r o ve s t h a t UG( D ) is 2 -c o n n e c t e d .
( ii) Th e s e c o n d c la im o f t h e le m m a is a n im m e d ia t e c o n s e qu e n c e o f t h e ¯ r s t c la im a n d

B yp a s s L e m m a . L e m m a 3 .3 is p r o ve d .

Refer ences

[1 ] J. B a n g -Je n s e n a n d G. Gu t in , D igraphs: Theory, Algorithms and Applications, S p r in g e r ,
2 0 0 1 .

[2 ] G. Gu t in , \ Cr it e r io n fo r c o m p le t e b ip a r t it e d ig r a p h s t o b e H a m ilt o n ia n " , Vestsi Akad,
Navuk B SSR Ser. F iz.-M at. Navuk vo l. 1 , p p . 1 0 9 -1 1 0 , 1 9 8 4 .



S. Darbinyan and I. Karapetyan 3 3

[3 ] G. Gu t in , \ Cyc le s a n d p a t h s in s e m ic o m p le t e m u lt ip a r t it e d ig r a p h s , t h e o r e m s a n d a l-
g o r it h m s : a s u r ve y" . J . Graph Theory vo l. 1 9 , n o . 4 , p p . 4 8 1 -5 0 5 , 1 9 9 5 .

[4 ] R . H Äa g g kvis t a n d Y . Ma n o u s s a kis , \ Cyc le s a n d p a t h s in b ip a r t it e t o u r n a m e n t s wit h
s p a n n in g c o n ¯ g u r a t io n s " . Combinatorica, vo l. 9 , n o . 1 , p p . 3 3 -3 8 , 1 9 8 9 .

[5 ] Y . Ma n o u s s a kis a n d I. Millis , \ A s u ± c ie n t c o n d it io n fo r m a xim u m c yc le s in b ip a r t it e
d ig r a p h s " , D iscrete M ath., vo l. 2 0 7 , p p . 1 6 1 -1 7 1 , 1 9 9 9 .

[6 ] J. A d a m u s a n d L . A d a m u s , \ A d e g r e e c o n d it io n fo r c yc le s o f m a xim u m le n g t h in b i-
p a r t it e d ig r a p h s " , D iscrete M ath., vo l. 3 1 2 , p p . 1 1 1 7 -1 1 2 2 , 2 0 1 2 .

[7 ] D . A m a r a n d Y . Ma n o u s s a kis , \ Cyc le s a n d p a t h s o f m a n y le n g t h s in b ip a r t it e d ig r a p h s " ,
J . Combin. Theory Ser. B 50, p p . 2 5 4 -2 6 4 , 1 9 9 0 .

[8 ] 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. and Theoretical Computer Science,vo l. 1 6 , n o . 1 ,
p p . 2 9 3 -3 0 2 , 2 0 1 4 .

[9 ] J. A d a m u s , \ A d e g r e e s u m c o n d it io n fo r h a m ilt o n ic it y in b a la n c e d b ip a r t it e d ig r a p h s " ,
Graphs and Combinatorics, vo l. 3 3 , n o . 1 , p p . 4 3 -5 1 , 2 0 1 7 .

[1 0 ] 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 " .
D iscrete M athematics and Theoretical Computer Science, vo l. 1 9 , n o . 3 , 2 0 1 7 .

[1 1 ] 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 m .CO] 2 9 , 1 5 p a g e s , A p r 2 0 1 6 .

[1 2 ] 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 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 e ve n
p a n c yc lic " , D iscrete Applied M athematics, vo l. 2 3 8 , p p . 7 0 -7 6 , 2 0 1 8 .

[1 3 ] M. Me s z ka , \ N e w s u ± c ie n t c o n d it io n s fo r b ip a n c yc lic it y o f b a la n c e d b ip a r t it e d ig r a p h s " ,
D iscrete M ath., S u b m it t e d fo r p u b lic a t io n .

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

[1 5 ] J. A d a m u s , \ A Me yn ie l-t yp e c o n d it io n fo r b ip a n c yc lic it y in b a la n c e d b ip a r t it e d i-
g r a p h s " , a r X iv:1 7 0 8 .0 4 6 7 4 v2 [m a t m .CO], 7 p a g e s , 2 2 A u g 2 0 1 7 .

[1 6 ] S . K h . D a r b in ya n , \ On p r e -H a m ilt o n ia n c yc le s in b a la n c e d b ip a r t it e d ig r a p h s " , M ath-
ematical problems of Computer Science, vo l. 4 6 , p p . 7 -1 7 , 2 0 1 4 .

[1 7 ] S . K h . D a r b in ya n a n d I. A . K a r a p e t ya n , \ A S u ± c ie n t c o n d it io n fo r p r e -H a m ilt o n ia n
Cyc le s in B ip a r t it e D ig r a p h s " , CSIT 2017 R evised Selected P apers,IE E E conference
proceeding,, p p . 1 0 1 -1 0 9 , D OI:1 0 .1 1 0 9 / CS ITTe c h n o l.2 0 1 7 .8 3 1 2 1 5 0 .

[1 8 ] O. Or e , \ Th e o r y o f g r a p h s " , A m e r ic a n Ma t h e m a t ic a l S o c ie t y, P r o vid e n c e , R .I., A m e r i-
c a n Ma t h e m a t ic a l S o c ie t y Co llo qu iu m P u b lic a t io n s , vo l. 3 8 , 1 9 6 2 .

[1 9 ] C. B e r g e , Graphs and hypergraphs, N o r t h -H o lla n d , A m s t e r d a m , 1 9 7 3 .

[2 0 ] J. A . B o n d y, B asic Graph Theory: P aths and Circuits, In H a n d b o o k o f c o m b in a t o r ic s
1-2, E ls e vie r , A m s t e r d a m , 1 9 9 5 .

Submitted 20.09.2017, accepted 16.01.2018.



3 4 On a Problem of Wang Concerning the Hamiltonicity of Bipartite Digraphs

ÎáÙÝáñáßí³Í »ñÏÙ³ëÝÛ³ ·ñ³ýÇ Ñ³ÙÇÉïáÝÛ³ÝáõÃÛ³Ý í»ñ³µ»ñÛ³É
ì³Ý·Ç ËݹñÇ Ù³ëÇÝ

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

²Ù÷á÷áõÙ

ì³Ý·Á (Discrete Mathematics and Theoretical Computer Science, vol. 19(3) 2017)
³é³ç³ñÏ»É ¿ Ñ»ï¨Û³É ËݹÇññ:

ÊݹÇñ: ¸Çóáõù D-Ý áõÅ»Õ Ï³å³Ïóí³Í 2 a-·³·³Ã³ÝÇ 2 a ¸ 8 ÏáÕÝáñáßí³Í
»ñÏÙ³ëÝÛ³ ѳí³ë³ñ³Ïßéí³Í ·ñ³ý ¿, áñáõÙ ·³·³ÃÝ»ñÇ ó³Ýϳó³Í fx; yg ѳÕÃáÕ
½áõÛ·Ç Ñ³Ù³ñ ï»ÕÇ áõÝ»Ý Ñ»ï¨Û³É ³Ýѳí³ë³ñáõÃÛáõÝÝ»ñÁ. d( x ) ¸ 2 a¡k, ¨ d( y ) ¸ a+k
ϳ٠d( x ) ¸ a + k ¨ d( y ) ¸ 2 a ¡ k, áñï»Õ 2 · k · a= 2 : ²ñ¹Ûáù D-Ý Ñ³ÙÇÉïáÝÛ³Ý ¿:

Ü»ñϳ ³ß˳ï³ÝùáõÙ ³å³óáõóí³Í ¿, áñ »Ã» D ·ñ³ýÁ µ³í³ñ³ñáõÙ ¿ ì³Ý·Ç
ËݹñÇ å³ÛÙ³ÝÝ»ñÇÝ, ³å³ (i) D ·ñ³ýÁ å³ñáõݳÏáõÙ ¿ óÇÏÉ-ý³Ïïáñ ¨ ³éÝí³½Ý
ãáñë »ñϳñáõÃÛ³Ùµ áã-ѳÙÇÉïáÝÛ³Ý óÇÏÉ, (ii) D ·ñ³ýÇ ó³Ýϳó³Í x ·³·³ÃÇ Ñ³Ù³ñ
·áÛáõÃÛáõÝ áõÝÇ ³ÛÝåÇëÇ ÙÇ y ·³·³Ã, áñ fx; yg - Á ѳÕÃáÕ ½áõÛ· ¿:

Î çàäà÷å Âàíãà î ãàìèëüòîíîâîñòè äâóäîëüíûõ îðãðàôîâ
Ñ. Äàðáèíÿí è È. Êàðàïåòÿí

Àííîòàöèÿ

Âàíã (Discrete Mathematics and Theoretical Computer Science, vol. 19(3) 2017)
ïðåäëîæèëà ñëåäóþùóþ çàäà÷ó.

Çàäà÷à: Ïóñòü D - 2 a -âåðøèííûé 2 a ¸ 8 ñèëüíîñâÿçíûé ñáàëàíñèðîâàííûé
äâóäîëüíûé îðãðàô, â êîòîðîì äëÿ ëþáîé ïàðû äîìèíèðóþùèõ âåðøèí fx; yg,
d( x ) ¸ 2 a ¡ k, d( y ) ¸ a + k èëè d( y ) ¸ a + k, d ( y ) ¸ 2 a ¡ k, ãäå 2 · k · a=2 . ßâëÿåòñÿ
ëè D ãàìèëüòîíîâûì?

 íàñòîÿùåé ðàáîòå äîêàçàíî, ÷òî åñëè îðãðàô D óäîâëåòâîðÿåò óñëîâèÿì
çàäà÷è Âàíãà, òî (i) D ñîäåðæèò öèêë-ôàêòîð è íå-ãàìèëüòîíîâûé öèêë äëèíû
ïî êðàéíåé ìåðå 4, (ii) äëÿ êàæäîé âåðøèíû x ñóùåñòâóåò òàêàÿ âåðøèíà y, ÷òî
fx; yg ÿâëÿåòñÿ äîìèíèðóþùèì ïàðîì.