Samvel_5--25.DVI


Mathematical Problems of Computer Science 43, 5{25, 2015.

On pr e-H amiltonian Cycles in H amiltonian 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 strongly connected directed graph of order n ¸ 4. In [14] (J. of Graph
Theory, Vol.16, No. 5, 51-59, 1992) Y. Manoussakis proved the following theorem:
Suppose that D satis¯es the following condition for every triple x; y; z of vertices such
that x and y are nonadjacent: If there is no arc from x to z, then d(x) + d(y) + d+(x) +
d¡(z) ¸ 3n¡2. If there is no arc from z to x, then d(x)+d(y)+d¡(x)+d+(z) ¸ 3n¡2.
Then D is Hamiltonian. In this paper we show that: If D satis¯es the condition of
Manoussakis' theorem, then D contains a pre-Hamiltonian cycle (i.e., a cycle of length
n ¡ 1) or n is even and D is isomorphic to the complete bipartite digraph with partite
sets of cardinalities n=2 and n=2.

Keywords: Digraphs, Cycles, Hamiltonian cycles, Pre-Hamiltonian cycles,
Longest non-Hamiltonian cycles.

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

A d ir e c t e d g r a p h ( 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 n, a n d is p a n c yc lic if it c o n t a in s c yc le s o f a ll le n g t h s m, 3 · m · n, wh e r e n is t h e
n u m b e r o f ve r t ic e s in D. W e r e c a ll t h e fo llo win g we ll-kn o wn d e g r e e c o n d it io n s ( Th e o r e m s
1 .1 -1 .8 ) wh ic h g u a r a n t e e t h a t a d ig r a p h is H a m ilt o n ia n . In e a c h o f t h e c o n d it io n s ( Th e o r e m s
1 .1 -1 .8 ) b e lo w D is a s t r o n g ly c o n n e c t e d d ig r a p h o f o r d e r n :

T heor em 1.1: ( Gh o u ila -H o u r i [1 2 ]) . If d ( x) ¸ n for all vertices x 2 V ( D ) , then D is
Hamiltonian.

T heor em 1.2: ( W o o d a ll [1 8 ]) . If d+ ( x ) + d¡ ( y ) ¸ n for all pairs of vertices x and y
such that there is no arc from x to y, then D is Hamiltonian.

T heor em 1.3: ( Me yn ie l [1 5 ]) . If n ¸ 2 and d( x ) + d( y ) ¸ 2 n ¡ 1 for all pairs of non-
adjacent vertices in D, then D is Hamiltonian.

It is e a s y t o s e e t h a t Me yn ie l's t h e o r e m is a c o m m o n g e n e r a liz a t io n o f Gh o u ila -H o u r i's
a n d W o o d a ll's t h e o r e m s . Fo r a s h o r t p r o o f o f Th e o r e m 1 .3 , s e e [5 ].

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

5



6 On pre-Hamiltonian Cycles in Hamiltonian Digraphs

T heor em 1.4: ( C. Th o m a s s e n [1 7 ], S . D a r b in ya n [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).

Fo r t h e n e xt t h e o r e m we n e e d t h e fo llo win g :
De¯nition 1: ( [1 4 ]) . L et k be an arbitrary nonnegative integer. A digraph D satis¯es the
condition Ak if and only if for every triple x; y; z of vertices such that x and y are nonadja-
cent: If there is no arc from x to z, then d ( x ) + d( y ) + d+ ( x ) + d¡ ( z ) ¸ 3 n ¡ 2 + k. If there
is no arc from z to x, then d ( x) + d ( y ) + d¡ ( x ) + d+ ( z ) ¸ 3 n ¡ 2 + k.

T heor em 1.5: ( Y . Ma n o u s s a kis [1 4 ]) . If a digraph D of order n ¸ 4 satis¯es the con-
dition A0, then D is Hamiltonian.

E a c h o f t h e s e t h e o r e m s 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 ) . Th e fo llo win g t h r e e t h e o r e m s im p o s e a d e g r e e c o n d it io n 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.6: ( B a n g -Je n s e n , Gu t in , H .L i [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-neighbour,
then D is Hamiltonian.

T heor em 1.7: ( B a n g -Je n s e n , Gu t in , H .L i [2 ]) .Suppose that minfd+ ( x ) + d¡ ( y ) ; d¡ ( x ) +
d+ ( y ) g ¸ n for any pair of nonadjacent vertices x; y with a common out-neighbour or a
common in-neighbour, then D is Hamiltonian.

T heor em 1.8: ( B a n g -Je n s e n , Gu o , Y e o [3 ]) . Suppose that d( x ) + d( y ) ¸ 2 n ¡ 1 and
minfd+ ( x ) + d¡ ( y ) ; d¡ ( x ) + d+ ( y ) g ¸ n ¡ 1 for any pair of nonadjacent vertices x; y with a
common out-neighbour or a common in-neighbour, then D is Hamiltonian.

N o t e t h a t Th e o r e m 1 .8 g e n e r a liz e s Th e o r e m 1 .7 .

In [1 1 , 1 6 , 6 , 8 ] it wa s s h o wn t h a t if a 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 o n e o f Th e o r e m s
1 .1 , 1 .2 , 1 .3 a n d 1 .4 , r e s p e c t ive ly, t h e n D a ls o 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 a t u r a l t o s e t t h e fo llo win g p r o b le m :

Characterize those digraphs which satisfy the conditions of Theorem 1.6 (1.7, 1.8) but
are not pancyclic.

In m a n y p a p e r s ( in t h e m e n t io n e d p a p e r s a s we ll) , t h e e xis t e n c e o f 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 n ¡ 1 ) is e s s e n t ia l t o t h e s h o w t h a t a g ive n d ig r a p h ( g r a p h ) is
p a n c yc lic o r n o t . Th is in d ic a t e s t h a t t h e e xis t e n c e o f a p r e -H a m ilt o n ia n c yc le in a d ig r a p h
( g r a p h ) in a s e n s e m a ke s t h e p a n c yc lic p r o b le m s ig n ī c a n t ly e a s ie r . Fo r t h 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 1 .6 o r 1 .7 o r 1 .8 in [9 ] a n d [1 0 ] t h e fo llo win g r e s u lt s a r e
p r o ve d :
(i) if the minimum semi-degree of a digraph D at least two and D satis¯es the conditions of
Theorem 1.6 or a digraph D is not a directed cycle and satis¯es the conditions of Theorem
1.7, then either D contains a pre-Hamiltonian cycle (i.e., a cycle of length n¡ 1 ) or n is even
and D is isomorphic to the complete bipartite digraph K¤n=2;n=2 or to the complete bipartite
digraph K¤n=2;n=2 minus one arc
(ii) if a digraph D is not a directed cycle and satis¯es the conditions of Theorem 1.8, then



S. Darbinyan and I. Karapetyan 7

D contains a pre-Hamiltonian cycle or a cycle of length n ¡ 2 .

In [1 4 ] t h e fo llo win g c o n je c t u r e wa s p r o p o s e d :

Conjectur e 1.9: Any strongly connected digraph satisfying the condition A3 is pancyclic.

In t h is p a p e r u s in g s o m e c la im s o f t h e p r o o f o f Th e o r e m 1 .5 ( s e e [1 4 ]) we p r o ve t h e fo l-
lo win g t h e o r e m :

T heor em 1.10: Any strongly connected digraph D on n ¸ 4 vertices satisfying the con-
dition A0 contains a pre-Hamiltonian cycle or n is even and D is isomorphic to the complete
bipartite digraph K¤n=2;n=2.

Th e fo llo win g e xa m p le s s h o w t h e s h a r p n e s s o f t h e b o u n d 3 n ¡ 2 in t h e t h e o r e m . Th e
d ig r a p h c o n s is t in g o f t h e d is jo in t u n io n o f t wo c o m p le t e d ig r a p h s wit h o n e c o m m o n ve r t e x
o r t h e d ig r a p h o b t a in e d fr o m a c o m p le t e b ip a r t it e d ig r a p h a ft e r d e le t in g o n e a r c s h o w t h a t
t h e b o u n d 3 n ¡ 2 in t h e a b o ve t h e o r e m is b e s t p o s s ib le .

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 ) a n d r e fe r t h e r e a d e r t o [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 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 o u t -n e ig h b o 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 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 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 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 . Fo r
a c yc le Ck := x1x2 ¢ ¢ ¢ xkx1 o f le n g t h k, t h e s u b s c r ip t s c o n s id e r e d m o d u lo k, i.e ., xi = xs fo r
e ve r y s a n d i s u c h t h a t i ´ s ( m o d k ) . 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 ( r e s p e c t ive ly,
a ll t h e ve r t ic e s o f D e xc e p t o n e ) is a H a m ilt o n ia n c yc le ( r e s p e c t ive ly, is a p r e -H a m ilt o n ia n
c yc le ) . Th e c o n c e p t o f t h e p r e -H a m ilt o n ia n c yc le wa s g ive n in [1 3 ]. If P is a p a t h c o n t a in in g
a s u b p a t h fr o m x t o y we le t P [x; y] d e n o t e t h a t s u b p a t h . S im ila r ly, if C is a c yc le c o n t a in in g
ve r t ic e s x a n d y, C[x; y] d e n o t e s t h e s u b p a t h o f C fr o m x t o y. 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. 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¤ t h e s ym m e t r ic



8 On pre-Hamiltonian Cycles in Hamiltonian Digraphs

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 . Kp;q
d e n o t e s t h e 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. 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. L e t C b e a n o n -H a m ilt o n ia n c yc le in d ig r a p h D. A n ( x; y ) -p a t h P is a C-b yp a s s if
jV ( P ) j ¸ 3 , x 6= y a n d V ( P ) \ V ( C ) = fx; yg.

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 L e m m a s 3 .1 -3 .4 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 3.1: [1 1 ]. L et D be a digraph of order n ¸ 3 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 ].

Th e fo llo win g le m m a is a s lig h t m o d i¯ c a t io n o f t h e le m m a b y B o n d y a n d To m a s s e n [5 ].

Lemma 3.2: L et D be a digraph of order n ¸ 3 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 xmx =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 an extended path from P with x).

If in L e m m a s 3 .1 a n d 3 .2 in s t e a d o f t h e ve r t e x x c o n s id e r a p a t h Q, t h e n we g e t t h e
fo llo win g L e m m a s 3 .3 a n d 3 .4 , r e s p e c t ive ly.

Lemma 3.3: L et Ck := x1x2 : : : xkx1, k ¸ 2 , be a non-Hamiltonian cycle in a digraph
D. M oreover, assume that there exists a path Q := y1y2 : : : yr, r ¸ 1 , in D ¡ Ck. If
d¡ ( y1; Ck ) + d

+ ( yr; Ck ) ¸ k + 1 , then for all m 2 [r + 1 ; k + r] the digraph D contains a cycle
Cm of length m with vertex set V ( Cm ) µ V ( Ck ) [ V ( Q) .

Lemma 3.4: L et P := x1x2 : : : xk, k ¸ 2 , be a non-Hamiltonian path in a digraph
D. M oreover, assume that there exists a path Q := y1y2 : : : yr, r ¸ 1 , in D ¡ P . If
d¡ ( y1; P ) + d

+ ( yr; P ) ¸ k + d¡ ( y1; fxkg ) + d+ ( yr; fx1g ) , then D contains a path from x1
to xk with vertex set V ( P ) [ V ( Q) .

Fo r t h e p r o o f o f o u r r e s u lt we a ls o n e e d t h e fo llo win g :

Lemma 3.5: ( [1 4 ]) . L et D be a digraph on n ¸ 3 vertices satisfying the condition A0.
Assume that there are two distinct pairs of nonadjacent vertices x; y and x; z in D. Then
either d( x ) + d( y ) ¸ 2 n ¡ 1 or d ( x ) + d ( z ) ¸ 2 n ¡ 1 .



S. Darbinyan and I. Karapetyan 9

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

In t h e p r o o f o f Th e o r e m 1 .1 0 we o ft e n will u s e t h e fo llo win g d e ¯ n it io n :

De¯nition 2: L et P0 := x1x2 : : : xm, m ¸ 2 , be an arbitrary ( x1; xm ) -path in a digraph
D and let y1; y2; : : : yk 2 V ( D ) ¡ V ( P0 ) . F or i 2 [1 ; k] we denote by Pi an ( x1; xm ) -path in
D with vertex set V ( Pi¡1 ) [ fyjg (if it exists) such that Pi is an extended path obtained from
Pi¡1 with some vertex yj, where yj =2 V ( Pi¡1). If e + 1 is the maximum possible number of
these paths P0; P1; : : : ; Pe, e 2 [0 ; k], then we say that Pe is an extended path obtained from P0
with vertices y1; y2; : : : ; yk as much as possible. Notice that Pi (i 2 [0 ; e]) is an ( x1; xm ) -path
of length m + i ¡ 1 .

P r oof of T heor em 1.10: L e t C := x1x2 : : : xkx1 b e a lo n g e s t n o n -H a m ilt o n ia n c yc le in
D o f le n g t h k, a n d le t C b e c h o s e n s o t h a t hV ( D ) ¡ V ( C ) i h a s t h e m in im u m n u m b e r o f
c o n n e c t e d c o m p o n e n t s . S u p p o s e t h a t k · n ¡ 2 a n d n ¸ 5 ( t h e c a s e n = 4 is t r ivia l) . It
is e a s y t o s h o w t h a t k ¸ 3 . W e will p r o ve t h a t D is is o m o r p h ic t o t h e 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. P u t R := V ( D ) ¡ V ( C ) . L e t R1; R2; : : : ; Rq b e t h e c o n n e c t e d c o m p o n e n t s
o f hRi ( i.e ., if q ¸ 2 , t h e n fo r a n y p a ir i; j, i 6= j, t h e r e is n o a r c b e t we e n Ri a n d Rj ) . In
[1 4 ] it wa s p r o ve d t h a t fo r a n y Ri, i 2 [1 ; q], t h e s u b d ig r a p h hV ( C ) [ V ( Ri ) i c o n t a in s a
C-b yp a s s . ( Th e e xis t e n c e o f a C-b yp a s s a ls o fo llo ws fr o m B yp a s s L e m m a ( s e e [4 ]) , s in c e
hV ( C ) [ V ( Ri ) i is s t r o n g a n d t h e c o n d it io n A0 im p lie s t h a t t h e u n d e r lyin g g r a p h o f t h e
s u b d ig r a p h hV ( C ) [ V ( Ri ) i is 2 -c o n n e c t e d ) . L e t P := xmy1y2 : : : yti xm+¸i b e a C-b yp a s s in
hV ( C ) [ V ( Ri ) i ( i 2 [1 ; q] is a r b it r a r y) a n d ¸i is c o n s id e r e d t o b e m in im u m in t h e s e n s e t h a t
t h e r e is n o C-b yp a s s xau1u2 : : : uli xa+ri in hV ( C ) [ V ( Ri ) i s u c h t h a t ri < ¸i a n d fxa; xa+rig
is a s u b s e t o f fxm; xm+1; : : : ; xm+¸ig.

W e will d is t in g u is h t wo c a s e s , a c c o r d in g a s t h e r e is a ¸i, i 2 [1 ; q], s u c h t h a t ¸i = 1 o r
n o t .

A s s u m e ¯ r s t t h a t ¸i ¸ 2 fo r a ll i 2 [1 ; q]. Fo r t h is c a s e o n e c a n s h o w t h a t ( t h e p r o o fs
a r e t h e s a m e a s t h e p r o o fs o f Ca s e 1 , L e m m a 2 .3 a n d Cla im 1 in [1 4 ]) if ¸i ¸ 2 , t h e n
ti = jRij = 1 , in hV ( C ) i t h e r e is a n ( xm+¸i ; xm ) -p a t h ( s a y, P 0 ) o f le n g t h k ¡ 2 wit h ve r t e x
s e t V ( P 0 ) = V ( C ) ¡ fzig, wh e r e zi 2 fxm+1; xm+2; : : : ; xm+¸i¡1g a n d d ( y1 ) + d ( zi ) · 2 n ¡ 2
( n o t e t h a t y1 a n d zi a r e n o n a d ja c e n t ) . Fr o m jRj ¸ 2 a n d jRij = 1 ( fo r a ll i) it fo llo ws t h a t
q ¸ 2 . If u 2 R2, t h e n d( u ) = d( u; C ) · k ( b y L e m m a 3 .1 ) a n d d( z1; R ) = 0 ( b y m in im a lit y
o f q ) , in p a r t ic u la r , t h e ve r t ic e s z1 a n d u a r e n o n a d ja c e n t . Th e r e fo r e , d( z1 ) = d( z1; C ) · k
a n d d( z1 ) +d( u ) · 2 n¡ 2 . Th is in c o n n e c t io n wit h d( y1 ) +d( z1 ) · 2 n¡ 2 c o n t r a d ic t s L e m m a
3 .5 .

A s s u m e s e c o n d t h a t ¸i = 1 fo r a ll i 2 [1 ; q]. It is c le a r t h a t q = 1 . P u t t := t1 a n d
¸ := ¸1 = 1 .

Ob s e r ve t h a t if v1v2 : : : vj ( m a yb e , j = 1 ) is a p a t h in hRi a n d xiv1 2 D, t h e n vj xi+j =2 D
s in c e C is t h e lo n g e s t n o n -H a m ilt o n ia n c yc le in D a n d k · n ¡ 2 . W e s h a ll u s e t h is o ft e n ,
wit h o u t m e n t io n in g t h is e xp lic it ly.

Th e fo llo win g c la im fo llo ws im m e d ia t e ly fr o m ¸ = 1 a n d t h e m a xim a lit y o f C.

Claim 1: R = fy1; y2; : : : ; ytg (i.e., t = n ¡ k ¸ 2 ), y1y2 : : : yt is a Hamiltonian path in
hRi and if 1 · i < j ¡ 1 · t ¡ 1 , then yiyj =2 D.

Fr o m Cla im 1 it fo llo ws t h a t

d+ ( y1; R) = d
¡ ( yt; R ) = 1 a n d if i 2 [1 ; t ¡ 1 ]; t h e n d+ ( yi; R ) · i; ( 1 )



1 0 On pre-Hamiltonian Cycles in Hamiltonian Digraphs

d ( y1; R ) ; d( yt; R ) · n ¡ k a n d if i 2 [2 ; t ¡ 1 ]; t h e n d ( yi; R ) · n ¡ k + 1 : ( 2 )
Claim 2: (i). If xiy1 2 D, then d¡ ( xi+1; fy1; y2; : : : ; yt¡1g ) = 0 ;
(ii). If ytxi+1 2 D, then d+ ( xi; fy2; y3; : : : ; ytg ) = d+ ( xi¡1; fy1; y2; : : : ; yt¡1g ) = 0 ;
(iii). d( y1; C ) · k, d( yt; C ) · k and d( yj; C ) · k ¡ 1 for all j 2 [2 ; t ¡ 1 ] (by L emma

3.2(iii) and Claim 2(ii) since ¸ = 1 ).
Claim 3: Assume that hRi is strong. If d+ ( xi; R ) ¸ 1 , d¡ ( xj; R) ¸ 1 and jC[xi; xj ]j ¸ 3

for some two distinct vertices xi; xj (i; j 2 [1 ; k]), then the following holds:
(i) d¡ ( xj¡1; R ) 6= 0 or A( R; C[xi+1; xj¡2]) 6= ;;
(ii) d+ ( xi+1; R) 6= 0 ) or A( R; C[xi+2; xj¡1]) 6= ;.
(Here if jC[xi; xj]j = 3 , then C[xi+1; xj¡2] = ; and C[xi+2; xj¡1] = ;).

P r oof of Claim 3: S u p p o s e t h a t Cla im 3 ( i) is fa ls e . 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 xkyf ; ygxl 2 D ( l 2 [2 ; k ¡ 1 ])

d¡ ( xl¡1; R ) = 0 a n d A ( R; C[x1; xl¡2]) = ;: ( 3 )

Th e s u b d ig r a p h hRi c o n t a in s a ( yf ; yg ) -p a t h ( s a y P ( yf ; yg ) ) s in c e R is s t r o n g . W e e xt e n d
t h e p a t h P0 := C[xl; xk] wit h t h e ve r t ic e s x1; x2; : : : ; xl¡1 a s m u c h a s p o s s ib le . Th e n s o m e
ve r t ic e s z1; z2; : : : ; xd 2 fx1; x2; : : : ; xl¡1g, d 2 [1 ; l ¡ 1 ], a r e n o t o n t h e e xt e n d e d p a t h Pe ( fo r
o t h e r wis e , it is n o t d i± c u lt t o s e e t h a t b y D e ¯ n it io n 2 t h e r e is a n ( xl; xk ) -p a t h Pi, i 2 [0 ; e],
wh ic h t o g e t h e r wit h t h e p a t h P ( yf ; yg ) a n d t h e a r c s xkyf ; ygxl fo r m s a n o n -H a m ilt o n ia n c yc le
lo n g e r t h a n C ) . Th e r e fo r e , b y L e m m a 3 .2 ( i) , fo r a ll s 2 [1 ; d] t h e fo llo win g h o ld s

d( zs; C ) · k + d ¡ 1 : ( 4 )

Fr o m ( 3 ) it fo llo ws t h a t y1xl¡1 =2 D a n d ytxl¡1 =2 D. H e n c e , b y L e m m a 3 .2 ( ii) , we h a ve

d( y1; C ) · k ¡ l + 2 a n d d( yt; C ) · k ¡ l + 2

s in c e n e it h e r y1 n o r yt c a n n o t b e in s e r t e d in t o C[xl¡1; xk]. Th is t o g e t h e r wit h ( 2 ) im p lie s
t h a t

d( y1 ) · n ¡ l + 2 a n d d( yt ) · n ¡ l + 2 : ( 5 )
If t h e r e e xis t s a zs s u c h t h a t d( zs; R) = 0 , t h e n b y d · l ¡ 1 , ( 4 ) a n d ( 5 ) we o b t a in t h a t

d( zs ) + d( y1 ) · 2 n ¡ 2 a n d d( zs ) + d ( yt ) · 2 n ¡ 2 ;

wh ic h c o n t r a d ic t s L e m m a 3 .5 s in c e zs; y1 a n d zs; yt a r e t wo d is t in c t p a ir s o f n o n a d ja c e n t
ve r t ic e s . A s s u m e , t h e r e fo r e , t h a t t h e r e is n o zs s u c h t h a t d( zs; R) = 0 . Th e n fr o m ( 3 ) it
fo llo ws t h a t d = 1 , z1 = xl¡1 a n d d

+ ( xl¡1; R) ¸ 1 . Th e r e fo r e , D c o n t a in s a n ( xl; xk ) -p a t h ,
s a y Q, wit h ve r t e x s e t V ( C ) ¡ fxl¡1g. S in c e hRi is s t r o n g , it fo llo ws t h a t in hRi t h e r e is a
( yf ; yg ) -p a t h , s a y T . Th is p a t h T t o g e t h e r wit h t h e p a t h Q a n d t h e a r c s xkyf , ygxl fo r m s a
c yc le C0 wh ic h d o e s n o t c o n t a in xl¡1. Fr o m t h e m a xim a lit y o f C it fo llo ws t h a t jT j = 1 ( i.e .,
yf = yg ) a n d

d+ ( xk; R ¡ fyf g ) = d¡ ( xl; R ¡ fyf g ) = 0 : ( 6 )
S o , t h e c yc le C0 h a s t h e le n g t h k a n d V ( C0 ) = V ( C ) [ fyf g ¡ fxl¡1g. It is n o t d if-
¯ c u lt t o s e e t h a t t h e ve r t ic e s xl¡1, yf a r e n o n a d ja c e n t ( fo r o t h e r wis e xl¡1yf 2 D a n d
xl¡1yf xl : : : xkx1 : : : xl¡1 is a c yc le o f le n g t h k + 1 , a c o n t r a d ic t io n ) . Fr o m t h is a n d



S. Darbinyan and I. Karapetyan 1 1

d¡ ( xl¡1; R) = 0 ( b y ( 3 ) ) we h a ve d ( xl¡1; R ) · n ¡ k ¡ 1 . Th is t o g e t h e r wit h d = 1 a n d ( 4 )
im p lie s t h a t d ( xl¡1 ) · n ¡ 1 .

A s s u m e ¯ r s t t h a t yf 6= y1.
L e t xl¡1y1 2 D. Th e n yf = yt ( b y Cla im 2 ( i) ) a n d fo r t h e t r ip le o f ve r t ic e s yt; xl¡1; y1

c o n d it io n A0 h o ld s , s in c e y1xl¡1 =2 D a n d yt; xl¡1 a r e n o n a d ja c e n t . S in c e ytxl 2 D, fr o m
( 3 ) a n d Cla im 2 ( ii) it fo llo ws t h a t d ( xl¡1; R ¡ fy1g ) = 0 , i.e ., d ( xl¡1; R ) = 1 . Th is t o g e t h e r
wit h ( 4 ) a n d d = 1 g ive s d ( xl¡1 ) · k + 1 . S in c e D c o n t a in s n o c yc le o f le n g t h k + 1 ,
it fo llo ws t h a t fo r t h e a r c xl¡1y1 a n d t h e c yc le C

0, b y L e m m a 3 .3 , t h e fo llo win g h o ld s
d¡ ( xl¡1; C

0 ) + d+ ( y1; C
0 ) · k. Th is t o g e t h e r wit h d+ ( y1; R) = 1 a n d d¡ ( xl¡1; R ) = 0 im p lie s

t h a t d¡ ( xl¡1 ) + d
+ ( y1 ) · n ¡ 2 ( h e r e we c o n s id e r t h e c a s e s k = n ¡ 2 a n d k · n ¡ 3

s e p a r a t e ly) . Th e r e fo r e , u s in g c o n d it io n A0, ( 5 ) , d ( xl¡1 ) · n ¡ 1 a n d l ¸ 2 we o b t a in

3 n ¡ 2 · d( yt ) + d( xl¡1 ) + d¡ ( xl¡1 ) + d+ ( y1 ) · 3 n ¡ 3 ;

a c o n t r a d ic t io n .
L e t n o w xl¡1y1 =2 D. Th e n b y ( 3 ) t h e ve r t ic e s xl¡1, y1 a r e n o n a d ja c e n t . Fr o m t h is t ¸ 3

s in c e yf ; xl¡1 a r e n o n a d ja c e n t a n d d
+ ( xl¡1; R) ¸ 1 . Th u s , we h a ve xky1 =2 D, y1xl =2 D ( b y

( 6 ) ) a n d d ( y1; C[x1; xl¡1]) = 0 . Th e r e fo r e , s in c e y1 c a n n o t b e in s e r t e d in t o C[xl; xk], u s in g
L e m m a 3 .2 ( iii) a n d ( 2 ) we o b t a in d ( y1 ) · n ¡ l. N o t ic e t h a t ( b y ( 2 ) a n d ( 4 ) )

d ( xl¡1 ) = d( xl¡1; C ) + d( xl¡1; R ¡ fy1; yf g ) · k + d( xl¡1; R ¡ fy1; yfg ) · n ¡ 2 ;

a n d ( b y L e m m a 3 .2 ( i) a n d d( yf ; C[x1; xl¡1]) = 0 ) ,

d( yf ) = d( yf ; C ) + d( yf ; R) · k ¡ l + 2 + d( yf ; R ) :

Fr o m t h e la s t t h r e e in e qu a lit ie s we o b t a in t h a t

d( y1 ) + d( xl¡1 ) · 2 n ¡ l ¡ 2 ;

a n d

d( yf ) + d( xl¡1 ) · 2 k ¡ l + 2 + d ( xl¡1; R ¡ fy1; yf g ) + d( yf ; R ) :
N o t ic e t h a t

d( xl¡1; R ¡ fy1; yfg ) + d ( yf ; R) · n ¡ k ¡ 2 + n ¡ k = 2 n ¡ 2 k ¡ 2

s in c e if xl¡1yj 2 D, t h e n yjyf =2 D, wh e r e yj 6= y1; yf . Th e la s t t wo in e qu a lit ie s g ive
d( yf ) + d( xl¡1 ) · 2 n¡l · 2 n¡ 2 . Th is t o g e t h e r wit h d( y1 ) + d( xl¡1 ) · 2 n ¡l ¡ 2 c o n t r a d ic t s
L e m m a 3 .5 s in c e xl¡1; y1 a n d xl¡1; yf a r e t wo d is t in c t p a ir s o f n o n a d ja c e n t ve r t ic e s .

A s s u m e n e xt t h a t yf = y1. If xl¡1; yt a r e n o n a d ja c e n t , t h e n d( xl¡1; fy1; ytg ) = 0 a n d
d( xl¡1; R ) · n ¡ k ¡ 2 . H e n c e , b y ( 4 ) a n d d = 1 we h a ve d ( xl¡1 ) · n ¡ 2 . Th is t o g e t h e r
wit h ( 5 ) im p lie s t h a t

d( y1 ) + d( xl¡1 ) · 2 n ¡ 2 a n d d ( yt ) + d ( xl¡1 ) · 2 n ¡ 2 ;

wh ic h c o n t r a d ic t s L e m m a 3 .5 , s in c e y1; xl¡1 a n d yt; xl¡1 a r e t wo d is t in c t p a ir s o f n o n a d ja c e n t
ve r t ic e s . S o , we c a n a s s u m e t h a t xl¡1yt 2 D. S in c e C0 is a lo n g e s t n o n -H a m ilt o n ia n c yc le ,
d¡ ( xl¡1; R) = 0 , ( 3 ) a n d d

+ ( yt; R ¡ fy1g ) · n ¡ k ¡ 2 , fr o m L e m m a 3 .3 it fo llo ws t h a t



1 2 On pre-Hamiltonian Cycles in Hamiltonian Digraphs

d¡ ( xl¡1 ) + d
+ ( yt ) · n ¡ 2 . N o w u s in g ( 5 ) , d( xl¡1 ) · n ¡ 1 a n d t h e c o n d it io n A0, fo r t h e

t r ip le o f t h e ve r t ic e s xl¡1; y1; yt we o b t a in

3 n ¡ 2 · d( y1 ) + d ( xl¡1 ) + d+ ( yt ) + d¡ ( xl¡1 ) · 3 n ¡ l ¡ 1 · 3 n ¡ 3 ;

wh ic h is a c o n t r a d ic t io n . Cla im 3 is p r o ve d .
In p a r t ic u la r , fr o m Cla im 3 im m e d ia t e ly fo llo ws t h e fo llo win g
Claim 4: Assume that hRi is strong and d+ ( xi; R) ¸ 1 , d¡ ( xj; R ) ¸ 1 for some two

distinct vertices xi and xj. Then the following holds:
(i) if jC[xi; xj]j ¸ 3 , then A ( R; C[xi+1; xj¡1]) 6= ;;
(ii) if jC[xi; xj]j = 3 , then d+ ( xi+1; R) ¸ 1 and d¡ ( xj¡1; R) ¸ 1 .

N o w we d ivid e t h e p r o o f o f t h e t h e o r e m in t o t wo p a r t s : k · n ¡ 3 a n d k = n ¡ 2 .

P art 1. k · n ¡ 3 , i.e., t ¸ 3 .
Fo r t h is p a r t ¯ r s t we will p r o ve t h e fo llo win g Cla im s 5 -1 0 b e lo w.

Claim 5: L et t ¸ 3 and yty1 2 D. Then the following holds
(i) if xiy1D, then d

¡ ( xi+2; R ) = 0 ; (ii) if ytxi 2 D, then d+ ( xi¡2; R) = 0 , where i 2 [1 ; k].
P r oof of Claim 5: ( 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 fo r s o m e i 2 [1 ; k] xiy1 2 D a n d

d¡ ( xi+2; R ) 6= 0 . 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 xi = x1 a n d d¡ ( x3; R ) 6= 0 .
Th e n d¡ ( x3; R ¡ fy1g ) = 0 a n d y1x3 2 D. It is e a s y t o s e e t h a t y1, x2 a r e n o n a d ja c e n t a n d

d¡ ( x2; fy1; y2; : : : ; yt¡1g ) = d+ ( x2; fy1; y3; y4; : : : ; ytg ) = 0 ; i.e ., d ( x2; R) · 2 : ( 7 )

S in c e n e it h e r y1 n o r x2 c a n b e in s e r t e d in t o C[x3; x1], u s in g ( 2 ) , ( 7 ) a n d L e m m a 3 .2 , we
o b t a in t h a t

d ( y1 ) = d( y1; C ) + d( y1; R ) · k + n ¡ k = n a n d d ( x2 ) = d( x2; C ) + d( x2; R ) · k + 2 :

On t h e o t h e r h a n d , b y L e m m a 3 .3 a n d ( 1 ) we h a ve t h a t d¡ ( yt ) + d
+ ( y1 ) · k + 2 s in c e t h e

a r c yty1 c a n n o t b e in s e r t e d in t o C. Th e r e fo r e , b y c o n d it io n A0, t h e fo llo win g h o ld s

3 n ¡ 2 · d( y1 ) + d( x2 ) + d¡ ( yt ) + d+ ( y1 ) · n + 2 k + 4 ;

s in c e y1; x2 a r e n o n a d ja c e n t a n d y1yt =2 D. Fr o m t h is a n d k · n¡ 3 it fo llo ws t h a t k = n ¡ 3 ,
x2y2; y2y1 2 D a n d h e n c e , t h e c yc le x2y2y1x3x4 : : : xkx1x2 h a s le n g t h k + 2 . Th is 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 C is a m a xim a l n o n -H a m ilt o n ia n c yc le .

To s h o w t h a t ( ii) is t r u e , it is s u ± c ie n t t o a p p ly t h e s a m e a r g u m e n t s t o t h e c o n ve r s e
d ig r a p h o f D. Cla im 5 is p r o ve d .

Claim 6: If t ¸ 3 and the vertices y1, yt are nonadjacent, then t = 3 and y3y2, y2y1 2 D.
P r oof of Claim 6: W it h o u t lo s s o f g e n e r a lit y, we c a n a s s u m e t h a t x1y1, ytx2 2 D ( s in c e

¸ = 1 ) .
A s s u m e ¯ r s t t h a t t ¸ 4 a n d ytyi 2 D fo r s o m e i 2 [2 ; t ¡ 2 ]. S in c e t h e a r c ytyi c a n n o t b e

in s e r t e d in t o C, u s in g L e m m a 3 .3 , we o b t a in

d¡ ( yt; C ) + d
+ ( yi; C ) · k: ( 8 )

Fr o m Cla im 1 a n d t h e c o n d it io n t h a t y1; yt a r e n o n a d ja c e n t it fo llo ws t h a t

d( y1; R) · n ¡ k ¡ 1 a n d d( yt; R) · n ¡ k ¡ 1 :



S. Darbinyan and I. Karapetyan 1 3

Th is t o g e t h e r wit h Cla im 2 ( iii) im p lie s t h a t d( y1 ) a n d d( yt ) · n ¡ 1 . S in c e y1; yt a r e
n o n a d ja c e n t a n d yiyt =2 D, u s in g ( 1 ) , ( 8 ) a n d a p p lyin g t h e c o n d it io n A0 t o t h e t r ip le o f t h e
ve r t ic e s y1; yt; yi, we o b t a in

3 n ¡ 2 · d ( y1 ) + d ( yt ) + d¡ ( yt; C ) + d+ ( yi; C ) + d¡ ( yt; R ) + d+ ( yi; R ) · 3 n ¡ 3 ;
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 t ¸ 4 a n d ytyi =2 D fo r a ll i 2 [2 ; t ¡ 2 ]. W e a ls o c a n a s s u m e t h a t
yiy1 =2 D fo r a ll i 2 [3 ; t ¡ 1 ]. Th e r e fo r e , d ( y1; R) · 2 a n d d( yt; R ) · 2 . Th is t o g e t h e r wit h
Cla im 2 ( iii) im p lie s t h a t d( y1 ) · k + 2 , d( yt ) · k + 2 a n d h e n c e

d ( y1 ) + d( yt ) · 2 k + 4 : ( 9 )
Fr o m t ¸ 4 a n d t h e a b o ve a s s u m p t io n s it fo llo ws t h a t y1; yt a n d y1; yt¡1 a r e t wo d is t in c t

p a ir s o f n o n a d ja c e n t ve r t ic e s . Fr o m ( 9 ) a n d k · n¡ 4 it fo llo ws t h a t d ( y1 ) +d( yt ) · 2 n¡ 4 . On
t h e o t h e r h a n d , s in c e d ( y1 ) · k+2 , d( yt¡1; C ) · k¡ 1 ( b y Cla im 2 ( iii) ) a n d d ( yt¡1; R ) · n¡k
( b y Cla im 1 ) , we h a ve

d ( y1 ) + d( yt¡1 ) · 2 n ¡ 3 :
Th is t o g e t h e r wit h d( y1 ) + d ( yt ) · 2 n ¡ 4 c o n t r a d ic t s L e m m a 3 .5 . W e , t h u s , p r o ve d t h a t t h e
c a s e t ¸ 4 is im p o s s ib le .

A s s u m e ¯ n a lly t h a t t = 3 . N o w we will s h o w t h a t y3y2 2 D. A s s u m e t h a t t h is is n o t
t h e c a s e , i.e ., y3y2 =2 D. Th e n we c a n a p p ly t h e c o n d it io n A0 t o t h e t r ip le o f t h e ve r t ic e s
y1; y3; y2, s in c e t h e ve r t ic e s y1; y3 a r e n o n a d ja c e n t a n d y3y2 =2 D. N o t ic e t h a t t h e a r c y2y3
c a n n o t b e in s e r t e d in t o C a n d h e n c e d¡ ( y2; C ) + d

+ ( y3; C ) · k ( b y L e m m a 3 .3 ) . Th e r e fo r e ,
b y A0 a n d Cla im 2 ( iii) , we o b t a in

3 n ¡ 2 · d ( y1 ) + d ( y3 ) + d¡ ( y2 ) + d+ ( y3 ) · 3 k + 4 · 3 n ¡ 5 ;
wh ic h is a c o n t r a d ic t io n . Th e r e fo r e y3y2 2 D.

S im ila r ly we o b t a in a c o n t r a d ic t io n if we a s s u m e t h a t y2y1 =2 D. Th e r e fo r e , y2y1 2 D.
Cla im 6 is p r o ve d .

Claim 7: If t ¸ 3 , then yty1 2 D.
P r oof of Claim 7: 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 ¸ 3 a n d yty1 =2 D, i.e ., y1; yt a r e

n o n a d ja c e n t . Th e n b y Cla im 6 , t = 3 a n d y3y2; y2y1 2 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 x1y1 a n d y3x2 2 D ( s in c e ¸ = 1 ) . N o t ic e t h a t d( y1 ) ; d ( y3 ) · n ¡ 1 ( b y L e m m a 3 .1 ) a n d
h e n c e , d( y1 ) + d( y3 ) · 2 n ¡ 2 . W e will d is t in g u is h t wo c a s e s , a c c o r d in g a s t h e r e is a n a r c
fr o m R t o fx3; x4; : : : ; xkg o r n o t .

Case 7.1. A( R ! fx3; x4; : : : ; xkg ) 6= ;.
Th e n t h e r e e xis t s a ve r t e x xl wit h l 2 [3 ; k] s u c h t h a t d¡ ( xl; R ) ¸ 1 a n d fo r l ¸ 4 ,

A ( R ! fx3; x4; : : : ; xl¡1g ) = ;.
If l = 3 , t h e n fr o m d¡ ( x3; fy2; y3g) = 0 it fo llo ws t h a t y1x3 2 D. Fr o m t h is it is e a s y t o s e e

t h a t d( x2; fy1; y2g ) = 0 . S in c e n e it h e r y1 n o r y3 a n d x2 c a n b e in s e r t e d in t o C[x3; x1] u s in g
L e m m a 3 .2 we o b t a in t h a t d ( y1 ) , d ( y3 ) a n d d( x2 ) · n ¡ 1 . H e n c e , d ( y1 ) + d( y3 ) · 2 n ¡ 2 a n d
d( y1 ) + d( x2 ) · 2 n ¡ 2 , wh ic h c o n t r a d ic t s L e m m a 3 .5 s in c e y1; y3 a n d y1; x2 a r e t wo d is t in c t
p a ir s o f n o n a d ja c e n t ve r t ic e s .

A s s u m e , t h e r e fo r e , t h a t l ¸ 4 . If d+ ( xl¡1; R) = 0 , t h e n d( xl¡1; R ) = 0 b y m in im a lit y
o f l. Th e r e fo r e , Cla im 4 im p lie s t h a t t h e r e is n o xi 2 C[x2; xl¡2] s u c h t h a t d+ ( xi; R ) ¸ 1 .
Th e r e fo r e , b y t h e m in im a lit y o f l we h a ve

A ( R; C[x3; xl¡1]) = ; a n d d+ ( x2; R) = 0 ;



1 4 On pre-Hamiltonian Cycles in Hamiltonian Digraphs

wh ic h c o n t r a d ic t s Cla im 3 ( ii) s in c e x1y1 2 D a n d d¡ ( xl; R) ¸ 1 . A s s u m e , t h e r e fo r e , t h a t
d+ ( xl¡1; R ) ¸ 1 . 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 ygxl 2 D a n d xl¡1yf 2 D.
It is e a s y t o s e e t h a t yf 6= yg, yf ; yg 2 fy1; y3g ( i.e ., xl¡1y2 =2 D a n d y2xl =2 D ) a n d t h e
ve r t ic e s xl¡1; xg a r e n o n a d ja c e n t .

A s s u m e ¯ r s t t h a t l = 4 . If yg = y3 ( i.e ., y3x4 2 D ) , t h e n x1y1y2y3x4 : : : xn¡3x1 is a c yc le
o f le n g t h n ¡ 1 , 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 yg = y1 a n d yf = y3, i.e ., y1x4 a n d
x3y3 2 D. Th e n t h e ve r t ic e s x2; y2 a r e c le a r ly n o n a d ja c e n t a n d x2y3 =2 D. S in c e y1x4 2 D
a n d d¡ ( x3; R ) = 0 , Cla im 4 ( ii) im p lie s t h a t x2y1 =2 D. Th e r e fo r e , d( x2; fy1; y2g ) = 0 . N o t ic e
t h a t x2 c a n n o t b e in s e r t e d in t o t h e p a t h C[x4; x1] ( fo r o t h e r wis e in D t h e r e is a c yc le o f
le n g t h n ¡ 3 wh ic h d o e s n o t c o n t a in t h e ve r t ic e s y2; y3; x3 b u t t h is c o n t r a d ic t s Cla im 6 s in c e
y2; x3 a r e n o n a d ja c e n t a n d y3x3 =2 D ) . N o w b y L e m m a 3 .2 a n d t h e a b o ve o b s e r va t io n we
o b t a in t h a t

d ( x2 ) = d( x2; C[x4; x1]) + d( x2; R ) + d( x2; fx3g ) · n ¡ 1 :
Th e r e fo r e , d ( y1 ) + d ( x2 ) · 2 n ¡ 2 , wh ic h t o g e t h e r wit h d( y1 ) + d( y3 ) · 2 n ¡ 2 c o n t r a d ic t s
L e m m a 3 .5 , s in c e y1; x2 a n d y1; y3 a r e t wo d is t in c t p a ir s o f n o n a d ja c e n t ve r t ic e s .

A s s u m e n e xt t h a t l ¸ 5 . Fr o m t h e m in im a lit y o f l, d¡ ( xl¡1; R ) = 0 a n d Cla im 4 ( ii) it
fo llo ws t h a t d ( xl¡2; R ) = 0 . Th e r e fo r e , t h e r e is n o xi 2 C[x2; xl¡2] s u c h t h a t d+ ( xi; R) ¸ 1 ,
in p a r t ic u la r , x2y3 =2 D. Th e r e fo r e

A( C[x3; xl¡2]; R) = ; a n d d( x2; R) = 1 ;

( o n ly y3x2 2 D ) . S in c e yg 6= y2 a n d xl¡1; yg a r e n o n a d ja c e n t , we h a ve d( xl¡1; R ) = 1 ( o n ly
xl¡1y4¡g 2 D ) . B y t h e a b o ve o b s e r va t io n we h a ve

d ( y1; C[x2; xl¡2]) = d ( y3; C[x3; xl¡2]) = 0 : ( 1 0 )

S in c e y1 c a n n o t b e in s e r t e d in t o C, x2y3 =2 D a n d d¡ ( xl¡1; R) = 0 , u s in g ( 1 0 ) a n d L e m m a
3 .2 we o b t a in t h a t d( y1; C ) · k ¡ l + 3 . Th is t o g e t h e r wit h d( y1; R ) = 2 im p lie s t h a t
d( y1 ) · k ¡ l + 5 .

N o w we e xt e n d t h e p a t h P0 := C[xl; x1] wit h t h e ve r t ic e s x2; x3; : : : ; xl¡1 a s m u c h a s
p o s s ib le . Th e n s o m e ve r t ic e s z1; z2; : : : ; zd 2 fx2; x3; : : : ; xl¡1g, d 2 [1 ; l ¡ 2 ], a r e n o t o n t h e
e xt e n d e d p a t h Pe. Th e r e fo r e , d( zi; C ) · k + d ¡ 1 a n d h e n c e , d( zi ) · k + d fo r a ll i 2 [1 ; d].
Th u s we h a ve d ( y1 ) + d ( zi ) · 2 n ¡ 3 a n d d ( y3 ) + d ( zi ) · 2 n ¡ 3 s in c e t h e r e is a ve r t e x zi
wh ic h is n o t a d ja c e n t t o y1 o r y3. Th is t o g e t h e r wit h d( y1 ) + d( y3 ) · 2 n ¡ 2 c o n t r a d ic t s
L e m m a 3 .5 s in c e y1; zi ( o r y3; zi ) a n d y1; y3 a r e t wo d is t in c t p a ir s o f n o n a d ja c e n t ve r t ic e s . In
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 d is c u s s io n o f Ca s e 7 .1 is c o m p le t e d .

Case 7.2. A( R ! fx3; x4; : : : ; xkg ) = ;.
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 A( fx3; x4; : : : ; xkg ! R ) = ; ( fo r

o t h e r wis e , we c o n s id e r t h e c o n ve r s e d ig r a p h o f D fo r wh ic h t h e c o n s id e r e d Ca s e 7 .1 h o ld s ) .
Th e r e fo r e A ( R; fx3; x4; : : : ; xkg) = ;. In p a r t ic u la r , xk is n o t a d ja c e n t t o t h e ve r t ic e s y1 a n d
y3. N o t ic e t h a t

d ( y1 ) = d( y1; R ) + d( y1; C ) · 2 + d( y1; fx1; x2g ) · 5 ;

d( y3 ) · 5 a n d d( xk ) = d ( xk; C ) · 2 n ¡ 8 . Th e r e fo r e d( xk ) + d( y1 ) · 2 n ¡ 3 a n d
d( xk ) + d ( y3 ) · 2 n ¡ 3 , wh ic h c o n t r a d ic t s L e m m a 3 .5 . Cla im 7 is p r o ve d .



S. Darbinyan and I. Karapetyan 1 5

Claim 8: If t ¸ 3 and for some i 2 [1 ; k] xiy1, then A ( R ! C[xi+2; xi¡1]) = ;.
P r oof of Claim 8: 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 . 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 x1y1 2 D a n d A( R ! fx3; x4; : : : ; xkg ) 6= ;. Th e n t h e r e is a ve r t e x xl
wit h l 2 [3 ; k] s u c h t h a t d¡ ( xl; R) ¸ 1 a n d if l ¸ 4 , t h e n A ( R ! fx3; x4; : : : ; xl¡1g ) = ;.
W e h a ve t h a t yty1 2 D ( b y Cla im 7 ) . In p a r t ic u la r , yty1 2 D im p lie s t h a t hRi is s t r o n g .
On t h e o t h e r h a n d , b y Cla im 5 ( i) , d¡ ( x3; R ) = 0 a n d h e n c e , l ¸ 4 . Fr o m x1y1 2 D it
fo llo ws t h a t t h e r e e xis t s a ve r t e x xr wit h r 2 [1 ; l ¡ 1 ] s u c h t h a t d+ ( xr; R ) ¸ 1 . Ch o o s e
r wit h t h e s e p r o p e r t ie s a s m a xim a l a s p o s s ib le . L e t xryf a n d ygxl 2 D. N o t ic e t h a t in
hRi t h e r e is a ( yf ; yg ) -p a t h s in c e hRi is s t r o n g . U s in g Cla im s 4 ( i) a n d 3 ( ii) we o b t a in
t h a t r = l ¡ 1 . Th e n yf 6= yg a n d in hRi a n y ( yf ; yg ) -p a t h is a H a m ilt o n ia n p a t h . S in c e
hRi is s t r o n g , fr o m d¡ ( xl¡1; R ) = 0 , d¡ ( xl; R) ¸ 1 a n d fr o m Cla im 3 ( i) it fo llo ws t h a t
A ( fx2; x3; : : : ; xl¡2g ! R) = ;, in p a r t ic u la r , d+ ( x2; R ) = 0 . B y t h e a b o ve o b s e r va t io n s we
h a ve

A ( fx3; x4; : : : ; xl¡2g; R ) = ;; d( y1; fx2; x3; : : : ; xl¡2g ) = d ( x2; fy1; y2; : : : ; yt¡1g ) = 0 : ( 1 1 )

N o t e t h a t x2, y1 a n d x2, y2 a r e t wo d is t in c t p a ir s o f n o n a d ja c e n t ve r t ic e s . W e e xt e n d t h e p a t h
P0 := C[xl; x1] wit h t h e ve r t ic e s x2; x3; : : : ; xl¡1 a s m u c h a s p o s s ib le . Th e n s o m e ve r t ic e s
z1; z2; : : : ; zd 2 fx2; x3; : : : ; xl¡1g, wh e r e d 2 [1 ; l ¡ 2 ], a r e n o t o n t h e e xt e n d e d p a t h Pe
( fo r o t h e r wis e , s in c e in hRi t h e r e is a ( yf ; yg ) -p a t h , u s in g t h e p a t h Pe¡1 o r Pe we o b t a in a
n o n -H a m ilt o n ia n c yc le lo n g e r t h a n C ) . B y L e m m a 3 .2 , fo r a ll i 2 [1 ; d] we h a ve

d ( zi; C ) · k + d ¡ 1 a n d d( zi ) = d( zi; C ) + d ( zi; R ) · k + d ¡ 1 + d( zi; R) : ( 1 2 )

A s s u m e t h a t t h e r e is a ve r t e x zi 6= xl¡1. Th e n , b y ( 1 1 ) , d ( zi; R ) · 1 ( s in c e d( x2; R) · 1 ) .
N o t ic e t h a t y1, zi a n d y2, zi a r e t wo d is t in c t p a ir s o f n o n a d ja c e n t ve r t ic e s ( b y ( 1 1 ) ) . S in c e
n e it h e r y1 n o r y2 c a n b e in s e r t e d in t o C[xl¡1; x1] a n d y1xl¡1 =2 D, y2xl¡1 =2 D, b y L e m m a
3 .2 ( ii) a n d ( 1 1 ) fo r j = 1 a n d 2 we o b t a in

d( yj; C ) = d ( yj ; C[xl¡1; x1]) · k ¡ l + 3 : ( 1 3 )

In p a r t ic u la r , b y ( 2 ) ,

d ( y1 ) = d( y1; C ) + d( y1; R ) · k ¡ l + 3 + n ¡ k = n ¡ l + 3 :

Th is t o g e t h e r wit h ( 1 2 ) a n d d( zi; R) · 1 im p lie s t h a t

d( y1 ) + d( zi ) · 2 n ¡ 2 ;

s in c e k · n ¡ 3 a n d d · l ¡ 2 . Th e r e fo r e , b y L e m m a 3 .5 , d( y2 ) + d( zi ) ¸ 2 n ¡ 1 . H e n c e , b y
( 2 ) a n d ( 1 2 ) we h a ve

2 n ¡ 1 · d( y2 ) + d( zi ) · n + d + d( zi; R) + d ( y2; C ) :

Fr o m t h is , d · l ¡ 2 a n d ( 1 3 ) it fo llo ws t h a t d( y2; C ) = k ¡ l + 3 , d( zi; R) = 1 a n d k = n ¡ 3 .
Th e n zi = x2 a n d ytx2 2 D ( b y ( 1 1 ) a n d d+ ( x2; R) = 0 ) . Th e r e fo r e , x1y2 =2 D. Fr o m t h is ,
y2xl¡1 =2 D a n d d ( y2; C ) = k ¡ l + 3 , b y L e m m a 3 .2 ( iii) , we c o n c lu d e t h a t y2 c a n b e in s e r t e d
in t o C, wh ic h is c o n t r a r y t o o u r s u p p o s it io n t h a t C is a lo n g e s t n o n -H a m ilt o n ia n c yc le .

N o w a s s u m e t h a t t h e r e is n o zi 6= xl¡1. Th e n d = 1 , z1 = xl¡1 a n d t h e r e is a n ( xl; x1 ) -
p a t h wit h ve r t e x s e t V ( C ) ¡ fxl¡1g. Th e r e fo r e , d¡ ( xl; fy2; y3; : : : ; ytg ) = 0 ( s in c e x1y1 2 D )



1 6 On pre-Hamiltonian Cycles in Hamiltonian Digraphs

a n d y1xl 2 D. Fr o m t h is we h a ve , d ( xl¡1; R ¡ fy2g ) = 0 s in c e yty1 2 D a n d l is m in im a l,
in p a r t ic u la r , t h e ve r t ic e s yt; xl¡1 a r e n o n a d ja c e n t . Th is t o g e t h e r wit h ( 1 2 ) im p lie s t h a t
d( xl¡1 ) · k + 1 ( o n ly xl¡1y2 2 D is p o s s ib le ) . N o t ic e t h a t n e it h e r yt n o r t h e a r c yty1 c a n b e
in s e r t e d in t o C, a n d t h e r e fo r e , b y L e m m a s 3 .2 , 3 .3 a n d b y ( 1 ) , ( 2 ) we o b t a in t h a t d ( yt ) · n
a n d d¡ ( yt ) + d

+ ( y1 ) · k + 2 . S in c e y1yt =2 D a n d yt; xl¡1 a r e n o n a d ja c e n t we h a ve t h a t t h e
t r ip le o f t h e ve r t ic e s yt; xl¡1, y1 s a t is ¯ e s c o n d it io n A0. Th e r e fo r e

3 n ¡ 2 · d( xl¡1 ) + d( yt ) + d¡ ( yt ) + d+ ( y1 ) · 3 n ¡ 3

s in c e k · n ¡ 3 , wh ic h is a c o n t r a d ic t io n . Cla im 8 is p r o ve d .

Claim 9: If t ¸ 3 , x1y1 and ytx2 2 D, then d¡ ( x1; R ) = 0 .
P r oof of Claim 9: A s s u m e t h a t d¡ ( x1; R ) ¸ 1 . B y Cla im 7 , yty1 2 D. N o w u s in g

Cla im s 5 ( ii) a n d 8 , we o b t a in t h a t d+ ( xk; R ) = 0 a n d

A ( R ! fx3; x4; : : : ; xkg) = ;: ( 1 4 )

In p a r t ic u la r , d( xk; R ) = 0 . Th is t o g e t h e r wit h d
¡ ( x1; R ) ¸ 1 , ( 1 4 ) a n d Cla im 3 im p lie s t h a t

A( fx2; x3; : : : ; xk¡1g ! R ) = ;. N o w a g a in u s in g ( 1 4 ) we g e t t h a t A( fx3; x4; : : : ; xkg; R ) = ;.
Th is t o g e t h e r wit h d+ ( x2; R ) = d

¡ ( x2; fy1; y2; : : : ; yt¡1g ) = 0 im p lie s t h a t d ( x2; R) = 1 ,
d( y2; C ) · 1 ( o n ly y2x1 2 D is p o s s ib le ) a n d d ( x3; R) = 0 . Th e r e fo r e , b y ( 2 ) ,

d ( y2 ) + d ( x3 ) = d( y2; C ) + d( y2; R ) + d( x3; R) + d ( x3; C ) · n + k · 2 n ¡ 3

a n d d( y2 ) + d( x2 ) · 2 n ¡ 2 , wh ic h c o n t r a d ic t s L e m m a 3 .5 s in c e y2; x3 a n d y2; x2 a r e t wo
d is t in c t p a ir s o f n o n a d ja c e n t ve r t ic e s . Th is c o m p le t e s t h e p r o o f o f Cla im 9 .

Claim 10: If t ¸ 3 , x1y1 and ytx2 2 D, then A ( fx3; x4; : : : ; xkg ! R) = ;.
P r oof of Claim 10: B y Cla im 7 , yty1 2 D. S u p p o s e t h a t A ( fx3; x4; : : : ; xkg ! R ) 6= ;.

R e c a ll t h a t Cla im 5 ( ii) im p lie s t h a t d+ ( xk; R ) = 0 . L e t xr, r 2 [3 ; k ¡ 1 ], b e c h o s e n s o t h a t
xryi 2 D fo r s o m e i 2 [1 ; t] a n d r is m a xim u m p o s s ib le . Th e n A( fxr+1; xr+2; : : : ; xkg; R) = ;
a n d d¡ ( x1; R) = 0 b y Cla im 8 a n d Cla im 9 , r e s p e c t ive ly. Th is t o g e t h e r wit h ytx2 2 D
c o n t r a d ic t s Cla im 3 ( i) . Cla im 1 0 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 p r o o f o f Th e o r e m 1 .1 0 fo r P a r t 1 ( wh e n k · n ¡ 3 ,
i.e ., t ¸ 3 ) . B y Cla im 7 , yty1 2 D. 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 x1y1 a n d
ytx2 2 D s in c e ¸ = 1 . Th e n fr o m Cla im s 8 , 9 a n d 1 0 it fo llo ws t h a t

A ( R ! fx3; x4; : : : ; xk; x1g ) = A( fx3; x4; : : : ; xkg ! R) = ;:

Fr o m t h is a n d
d¡ ( x2; fy1; y2; : : : ; yt¡1g ) = d+ ( x1; fy2; y3; : : : ; ytg ) = 0

we o b t a in t h a t x1; y2 a n d x1; yt a r e t wo d is t in c t p a ir s o f n o n a d ja c e n t ve r t ic e s a n d d ( y2; C ) · 1 ,
d( yt; C ) · 2 , d ( x1; R ) = 1 . Th e r e fo r e , d( y2 ) · n ¡ k + 2 , d( yt ) · n ¡ k + 2 ( b y ( 2 ) )
a n d d( x1 ) · 2 k ¡ 1 . Th e la s t t h r e e in e qu a lit ie s im p ly t h a t d( y2 ) + d( x1 ) · 2 n ¡ 2 a n d
d( yt ) + d ( x1 ) · 2 n ¡ 2 , wh ic h c o n t r a d ic t s L e m m a 3 .5 a n d c o m p le t e s t h e d is c u s s io n o f P a r t
1 .

P art 2. k = n ¡ 2 , i.e., t = 2 .



S. Darbinyan and I. Karapetyan 1 7

Fo r t h is p a r t ¯ r s t we will p r o ve Cla im s 1 1 -1 6 b e lo w.

Claim 11: If xiyf 2 D and y2y1 =2 D, where i 2 [1 ; n ¡ 2 ] and f 2 [1 ; 2 ], then there is
no l 2 [3 ; n ¡ 2 ] such that yf xi+l¡1 2 D and d ( yf ; fxi+1; xi+2; : : : ; xi+l¡2g ) = 0 .

P r oof of Claim 11: 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 xiyf ; yf xi+l¡1 2 D
a n d d( yf ; fxi+1; xi+2; : : : ; xi+l¡2g ) = 0 fo r s o m e l 2 [3 ; n ¡ 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 xi = x1. Th e n x1yf , yf xl 2 D a n d d( yf ; fx2; x3; : : : ; xl¡1g ) = 0 . S in c e D
c o n t a in s n o c yc le o f le n g t h n ¡ 1 , u s in g L e m m a s 3 .2 a n d 3 .3 , we o b t a in t h a t

d¡ ( y1 ) + d
+ ( y2 ) · n ¡ 2 a n d d ( yf ) · n ¡ l + 2 : ( 1 5 )

W e e xt e n d t h e p a t h P0 := C[xl; x1] wit h t h e ve r t ic e s x2; x3; : : : ; xl¡1 a s m u c h a s p o s s ib le .
Th e n s o m e ve r t ic e s z1; z2; : : : ; zd 2 fx2; x3; : : : ; xl¡1g, d 2 [1 ; l ¡ 2 ], a r e n o t o n t h e e xt e n d e d
p a t h Pe. Th e r e fo r e , b y L e m m a 3 .2 , d( z1 ) = d( z1; C ) + d( z1; fy3¡f g ) · n + d ¡ 1 . N o w, s in c e
t h e ve r t ic e s yf ; z1 a r e n o n a d ja c e n t a n d y2y1 =2 D, b y c o n d it io n A0 a n d ( 1 5 ) we h a ve

3 n ¡ 2 · d( yf ) + d ( z1 ) + d¡ ( y1 ) + d+ ( y2 ) · 3 n ¡ 3 ;

a c o n t r a d ic t io n . Cla im 1 1 is p r o ve d .

Claim 12: y2y1 2 D (i.e., if k = n ¡ 2 , then hV ( D ) ¡ V ( C ) i is strong).
P r oof of Claim 12: S u p p o s e , o n t h e c o n t r a r y, t h a t y2y1 =2 D. 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 x1y1 2 D a n d t h e ve r t ic e s y1; x2 a r e n o n a d ja c e n t . Th e n y2x3 =2 D a n d
s in c e D c o n t a in s n o c yc le o f le n g t h n ¡ 1 , u s in g L e m m a 3 .3 fo r t h e a r c y1y2 we o b t a in t h a t

d¡ ( y1 ) + d
+ ( y2 ) · n ¡ 2 : ( 1 6 )

Case 12.1. d+ ( y1; C[x3; xn¡2]) ¸ 1 .
L e t xl, l 2 [3 ; n ¡ 2 ], b e c h o s e n s o t h a t y1xl 2 D a n d l is m in im u m , i.e .,

d+ ( y1; C[x2; xl¡1]) = 0 . It is e a s y t o s e e t h a t t h e ve r t ic e s y1 a n d xl¡1 a r e n o n a d ja c e n t .
B y Cla im 1 1 , we c a n a s s u m e t h a t l ¸ 5 ( if l · 4 , t h e n d( y1; C[x2; xl¡1]) = 0 , a c o n t r a d ic -
t io n t o Cla im 1 1 ) a n d d¡ ( y1; C[x3; xl¡2]) ¸ 1 . It fo llo ws t h a t t h e r e e xis t s a ve r t e x xr wit h
r 2 [3 ; l ¡ 2 ] s u c h t h a t xry1 2 D a n d d ( y1; C[xr+1; xl¡1]) = 0 . Co n s e qu e n t ly, fo r t h e ve r t ic e s
y1, xr a n d xl Cla im 1 1 is n o t t r u e , a c o n t r a d ic t io n .

Case 12.2. d+ ( y1; C[x3; xn¡2]) = 0 .
Th e n d+ ( y1; C[x2; xn¡2]) = 0 a n d e it h e r y1x1 2 D o r y1x1 =2 D.
Subcase 12.2.1. y1x1 2 D.
Th e n xn¡2y1 =2 D a n d h e n c e , t h e ve r t ic e s y1; xn¡2 a r e n o n a d ja c e n t . Th e r e fo r e , t h e t r ip le o f

t h e ve r t ic e s y1; xn¡2, y2 s a t is ¯ e s t h e c o n d it io n A0. Cla im 1 1 im p lie s t h a t d
¡ ( y1; C[x2; xn¡2]) =

0 . Th is t o g e t h e r wit h d+ ( y1; C[x2; xn¡2]) = 0 a n d y2y1 =2 D g ive s d( y1 ) = 3 . Cle a r ly,
d( x2 ) · 2 n ¡ 4 a n d h e n c e , fo r t h e ve r t ic e s y1; y2; x2 b y c o n d it io n A0 a n d ( 1 6 ) we h a ve ,

3 n ¡ 2 · d( y1 ) + d ( x2 ) + d¡ ( y1 ) + d+ ( y2 ) · 3 n ¡ 3 ;

wh ic h is a c o n t r a d ic t io n .
Subcase 12.2.2. y1x1 =2 D.
Th e n d+ ( y1; C ) = 0 , d

+ ( y1 ) = 1 a n d d
+ ( y2; C ) ¸ 1 s in c e D is s t r o n g . 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 d¡ ( y2; C ) = 0 ( fo r o t h e r wis e fo r t h e ve r t e x y2 in t h e c o n ve r s e
d ig r a p h o f D we wo u ld h a ve t h e a b o ve c o n s id e r e d Ca s e 1 2 .1 o r S u b c a s e 1 2 .2 .1 ) . S in c e t h e



1 8 On pre-Hamiltonian Cycles in Hamiltonian Digraphs

t r ip le o f t h e ve r t ic e s y1; y2; x3 s a t is ¯ e s t h e c o n d it io n A0, d ( y1 ) · n ¡ 2 , d ( x2 ) · 2 n ¡ 5 a n d
( 1 6 ) , it is n o t d i± c u lt t o s h o w t h a t n ¸ 7 .

S u p p o s e ¯ r s t t h a t y2x2 2 D. Th e n xn¡2y1 =2 D a n d h e n c e , t h e ve r t ic e s xn¡2; y1 a r e
n o n a d ja c e n t .

L e t fo r s o m e l 2 [3 ; n ¡ 3 ] xly1 2 D a n d d¡ ( y1; C[xl+1; xn¡2]) = 0 . Th e n
d( y1; C[xl+1; xn¡2]) = 0 a n d d ( y1 ) · l s in c e d+ ( y1; C ) = 0 a n d x2; y1 a r e n o n a d ja c e n t .
E xt e n d t h e p a t h P0 := C[x2; xl] wit h t h e ve r t ic e s xl+1; xl+2; : : : ; xn¡2; x1 a s m u c h a s p o s -
s ib le . Th e n s o m e ve r t ic e s z1; z2; : : : ; zd 2 fxl+1; xl+2; : : : ; xn¡2; x1g, d 2 [2 ; n ¡ l ¡ 1 ],
a r e n o t o n t h e e xt e n d e d p a t h Pe. Fo r a ve r t e x zi 6= x1 b y L e m m a 3 .2 we o b t a in t h a t
d( zi ) = d( zi; C ) + d( zi; fy2g ) · n + d ¡ 1 . Th e r e fo r e , s in c e y2y1 =2 D a n d t h e ve r t ic e s zi; y1
a r e n o n a d ja c e n t , b y c o n d it io n A0 a n d ( 1 6 ) , we g e t t h a t

3 n ¡ 2 · d( y1 ) + d( zi ) + d¡ ( y1 ) + d+ ( y2 ) · 3 n ¡ 4 ;

wh ic h is a c o n t r a d ic t io n .
L e t n o w xly1 =2 D fo r a ll l 2 [3 ; n ¡ 2 ], i.e ., d¡ ( y1; C[x3; xn¡2]) = 0 . Th e n fr o m

d+ ( y1; C[x2; xn¡2]) = 0 , y1x1 =2 D a n d xn¡2y2 =2 D ( s in c e d¡ ( y2; C ) = 0 ) it fo llo ws t h a t
d( y1 ) = 2 a n d d( xn¡2 ) · 2 n ¡ 5 . Fr o m t h is , s in c e t h e ve r t ic e s y1, xn¡2 a r e n o n a d ja c e n t a n d
y2y1 =2 D, b y c o n d it io n A0 a n d ( 1 6 ) we h a ve t h a t

3 n ¡ 2 · d( y1 ) + d( xn¡2 ) + d¡ ( y1 ) + d+ ( y2 ) · 3 n ¡ 5 ;

wh ic h is a c o n t r a d ic t io n .

S u p p o s e n e xt t h a t y2x2 =2 D. Th e n d( y2; fx2; x3g ) = 0 , s in c e d¡ ( y2; C ) = 0 .
L e t fo r s o m e l 2 [4 ; n¡ 2 ] y2xl 2 D a n d d+ ( y2; C[x2; xl¡1]) = 0 . Th e n d ( y2; C[x2; xl¡1]) = 0

a n d t h e ve r t ic e s y1, xl¡2 a r e n o n a d ja c e n t s in c e d
+ ( y1; C[x2; xn¡2]) = 0 . It is e a s y t o s e e t h a t

t h e r e e xis t s a ve r t e x xr 2 fx1; x2; : : : ; xl¡3g s u c h t h a t xry1 2 D a n d d( y1; C[xr+1; xl¡2]) = 0 .
Th u s , we h a ve t h a t A( R; C[xr+1; xl¡2]) = ;. N o t ic e t h a t d( y2 ) · n ¡ l + 1 s in c e
d¡ ( y2; C ) = 0 a n d d ( y2; C[x2; xl¡1]) = 0 . W e e xt e n d t h e p a t h P0 := C[xl; xr] wit h
t h e ve r t ic e s xr+1; xr+2; : : : ; xl¡1 a s m u c h a s p o s s ib le . Th e n s o m e ve r t ic e s z1; z2; : : : ; zd 2
fxr+1; xr+2; : : : ; xl¡1g, d 2 [2 ; l ¡ r ¡ 1 ], a r e n o t o n t h e e xt e n d e d p a t h Pe. Th e r e fo r e , b y
L e m m a 3 .2 fo r zi 6= xl¡1 we h a ve , d( zi ) · n + d¡ 3 . N o w b y c o n d it io n A0 a n d ( 1 6 ) we o b t a in

3 n ¡ 2 · d( y2 ) + d( zi ) + d¡ ( y1 ) + d+ ( y2 ) < 3 n ¡ 3 ;

a c o n t r a d ic t io n .
L e t n o w d+ ( y2; fx2; x3; : : : ; xn¡2g ) = 0 . Th e n d ( y2 ) = 2 , d ( x2 ) · 2 n ¡ 6 a n d t h e ve r t ic e s

x2; y2 a r e n o n a d ja c e n t . B y c o n d it io n A0 we h a ve

3 n ¡ 2 · d( y2 ) + d( x2 ) + d¡ ( y1 ) + d+ ( y2 ) < 3 n ¡ 3 ;

a c o n t r a d ic t io n . Cla im 1 2 is p r o ve d .

Claim 13: F or any i 2 [1 ; n ¡ 2 ] and f 2 [1 ; 2 ] the following holds
i) d¡ ( yf ; fxi¡1; xig ) · 1 and ii) d+ ( yf ; fxi¡1; xig) · 1 .
P r oof of Claim 13: Th e p r o o f is b y c o n t r a d ic t io n . B y Cla im 1 2 , y2y1 2 D. 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 xn¡3y1, xn¡2y1 2 D a n d y1; x1 a r e n o n a d ja c e n t . It is
e a s y t o s e e t h a t d+ ( y2; fx1; x2g ) = 0 , y1xn¡2 =2 D a n d y1x2 =2 D ( fo r o t h e r wis e , if y1x2 2 D,



S. Darbinyan and I. Karapetyan 1 9

t h e n xn¡2y1x2x3 : : : xn¡3 xn¡2 is a c yc le o f le n g t h n ¡ 2 fo r wh ic h hfy2; x1gi is n o t s t r o n g , a
c o n t r a d ic t io n t o Cla im 1 2 ) . Th e r e fo r e , A( R ! fx1; x2g ) = ;. A g a in u s in g Cla im 1 2 , it is
n o t d i± c u lt t o c h e c k t h a t n ¸ 6 .

A s s u m e ¯ r s t t h a t A( R ! fx3; x4; : : : ; xn¡3g ) 6= ;. N o w le t xl, l 2 [3 ; n ¡ 3 ], b e t h e
¯ r s t ve r t e x a ft e r x2 t h a t d

¡ ( xl; R ) ¸ 1 . Th e n A ( R ! fx1; x2; : : : ; xl¡1g ) = ; s in c e A( R !
fx1; x2g ) = ; ( in p a r t ic u la r , d¡ ( xl¡1; R) = ; ) . Fr o m t h e m in im a lit y o f l a n d xn¡2y1 2 D
it fo llo ws t h a t t h e r e is a ve r t e x xr 2 fxn¡2; x1; x2; : : : ; xl¡2g s u c h t h a t d+ ( xr; R) ¸ 1 a n d
A ( fxr+1; xr+2; : : : ; xl¡2g; R) = ; ( if xr = xn¡2, t h e n xr+1 = x1 ) . Th is c o n t r a d ic t s Cla im 3 ( i)
s in c e d¡ ( xl¡1; R ) = 0 a n d hRi is s t r o n g .

A s s u m e n e xt t h a t A( R ! fx3; x4; : : : ; xn¡3g ) = ;. Th is t o g e t h e r wit h A ( R ! fx1; x2g ) =
; g ive s t h a t A ( R ! fx1; x2; : : : ; xn¡3g ) = ;. Fr o m t h is , s in c e D is s t r o n g a n d y1xn¡2 =2 D,
it fo llo ws t h a t y2xn¡2 2 D. Th e n xn¡3y2 =2 D a n d xn¡4y1 =2 D. N o w u s in g Cla im 1 2 we
o b t a in t h a t d( y2; fxn¡4; xn¡3g ) = 0 . S in c e d¡ ( xn¡3; R) = 0 a n d y2xn¡2 2 D, fr o m Cla im 3 ( i)
it fo llo ws t h a t d+ ( xn¡4; R ) = 0 . Th e r e fo r e , d ( xn¡4; R) = 0 . If A ( fx1; x2; : : : ; xn¡5g !
R ) 6= ;, t h e n t h e r e is a ve r t e x xr wit h r 2 [1 ; n ¡ 5 ] s u c h t h a t d+ ( xr; R ) ¸ 1 a n d
A ( R; fxr+1; xr+2; : : : ; xn¡4g ) = ; ( n ¸ 6 ) wh ic h c o n t r a d ic t s Cla im 3 ( i) , s in c e y2xn¡2 2 D
a n d d¡ ( xn¡3; R ) = 0 . A s s u m e t h e r e fo r e t h a t A ( fx1; x2; : : : ; xn¡4g ! R) = ;. Th u s , we h a ve
t h a t A ( fx1; x2; : : : ; xn¡4g; R ) = ; a n d d¡ ( xn¡3; R) = 0 . Th e n d( y1 ) = 4 , d( y2 ) · 4 a n d
d( x1 ) · 2 n ¡ 6 . Fr o m t h is it fo llo ws t h a t d ( y1 ) + d( x1 ) · 2 n ¡ 2 a n d d( y2 ) + d ( x1 ) · 2 n ¡ 2
wh ic h c o n t r a d ic t s L e m m a 3 .5 . Th is c o n t r a d ic t io n p r o ve s t h a t d¡ ( yf ; fxi¡1; xig ) · 1 fo r a ll
i 2 [1 ; n ¡ 2 ] a n d f 2 [1 ; 2 ]. S im ila r ly, o n e c a n s h o w t h a t d+ ( yf ; fxi¡1; xig ) · 1 . Cla im 1 3 is
p r o ve d .

Claim 14: If xiyf 2 D (respectively, yf xi 2 D), then d ( yf ; fxi+2g ) 6= 0 (respectively,
d( yf ; fxi¡2g ) 6= 0 ), where i 2 [1 ; n ¡ 2 ] and f 2 [1 ; 2 ].

P r oof of Claim 14: 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 . B y Cla im 1 2 , y2y1 2 D.
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 xn¡2y1 2 D a n d d( y1; fx2g ) = 0 , i.e .,
t h e ve r t ic e s y1 a n d x2 a r e n o n a d ja c e n t . Cla im 1 3 im p lie s t h a t t h e ve r t ic e s y1; x1 a ls o a r e
n o n a d ja c e n t . Th u s , d( y1; fx1; x2g ) = 0 . N o t e t h a t y2x2 =2 D a n d h e n c e , d¡ ( x2; R) = 0 . N o w
it is n o t d i± c u lt t o c h e e k t h a t if n = 5 , t h e n d( y1 ) + d( x1 ) · 8 a n d d( y1 ) + d( x2 ) · 8 , a
c o n t r a d ic t io n t o L e m m a 3 .5 .

A s s u m e , t h e r e fo r e , t h a t n ¸ 6 a n d c o n s id e r t h e fo llo win g c a s e s .
Case 14.1. A( R ! fx3; x4; : : : ; xn¡3g) 6= ;.
Th e n t h e r e is a ve r t e x xl wit h l 2 [3 ; n ¡ 3 ] s u c h t h a t d¡ ( xl; R ) ¸ 1 a n d A( R !

fx2; x3; : : : ; xl¡1g ) = ; s in c e d( y1; fx1; x2g ) = d¡ ( x2; R ) = 0 . W e n o w c o n s id e r t h e c a s e l = 3
a n d t h e c a s e l ¸ 4 s e p a r a t e ly.

A s s u m e t h a t l = 3 . Th e n y2x3 2 D o r y1x3 2 D.
L e t y2x3 2 D. Th e n t h e ve r t ic e s y2; x2 a r e n o n a d ja c e n t . S in c e t h e ve r t ic e s y1; x2 a r e

n o n a d ja c e n t Cla im 1 2 im p lie s t h a t x1y2 =2 D ( fo r o t h e r wis e xn¡2x1y2x3 : : : xn¡4xn¡2 is a
c yc le o f le n g t h n ¡ 2 wh ic h d o e s n o t c o n t a in t h e ve r t ic e s y1; x2 a n d hfy1; x2gi is n o t s t r o n g ,
a c o n t r a d ic t io n t o Cla im 1 2 ) . Th is c o n t r a d ic t s Cla im 3 ( ii) b e c a u s e o f d( x2; R) = 0 a n d
d+ ( x1; R ) = 0 .

L e t n o w y1x3 2 D a n d y2x3 =2 D. Th e n it is e a s y t o s e e t h a t x1y2 =2 D a n d y2x2 =2 D.
Fr o m t h is a n d Cla im 1 2 im p lie s t h a t n e it h e r x1 n o r x2 c a n b e in s e r t e d in t o C[x3; xn¡2].
N o t ic e t h a t if x2y2 2 D, t h e n xn¡2x2 =2 D, a n d if y2x1 2 D, t h e n x1x3 =2 D. N o w u s in g
L e m m a 3 .2 , we o b t a in t h a t d( y1 ) , d ( x1 ) a n d d( x2 ) · n¡ 1 s in c e d ( y1; fx1; x2g) = 0 . Th e r e fo r e

d( y1 ) + d( x1 ) · 2 n ¡ 2 a n d d( y1 ) + d( x2 ) · 2 n ¡ 2 ;



2 0 On pre-Hamiltonian Cycles in Hamiltonian Digraphs

wh ic h c o n t r a d ic t s L e m m a 3 .5 s in c e y1; x1 a n d y1; x2 a r e t wo d is t in c t p a ir s o f n o n a d ja c e n t
ve r t ic e s . Th is c o n t r a d ic t io n c o m p le t e s t h e d is c u s s io n o f Ca s e 1 4 .1 wh e n l = 3 .

A s s u m e t h a t l ¸ 4 . L e t ygxl 2 D, wh e r e g 2 [1 ; 2 ]. Th e n , b y t h e m in im a lit y o f l,
t h e ve r t ic e s yg; xl¡1 a r e n o n a d ja c e n t , y3¡gxl¡1 =2 D a n d xl¡2y3¡g =2 D. H e n c e , b y Cla im
1 2 we g e t t h a t xl¡2yg =2 D. Fr o m t h e m in im a lit y o f l a n d d¡ ( x2; R ) = 0 ( fo r l = 4 ) it
fo llo ws t h a t xl¡2 is n o t a d ja c e n t t o y1 a n d y2, i.e ., d( xl¡2; R ) = 0 . Th is t o g e t h e r wit h
d¡ ( x2; R ) = d

¡ ( xl¡1; R) = 0 , t h e m in im a lit y o f l a n d Cla im 3 ( i) im p lie s t h a t

A ( R; fx2; x3; : : : ; xl¡2g ) = ; a n d d+ ( x1; R) = 0

( if d+ ( x1; R) ¸ 1 , t h e n l ¸ 5 a n d t h e r e is a n xr wit h r 2 [1 ; l¡ 3 ] s u c h t h a t d+ ( xl¡1; R) = 0 a n d
A( R; C[xr+1; xl¡3]) = ; b u t t h is c o n t r a d ic t s Cla im 3 ( i) ) . If d¡ ( x1; R ) = 0 o r d+ ( xl¡1; R) = 0 ,
t h e n d( x1; R ) = 0 o r d ( xl¡1; R ) = 0 , r e s p e c t ive ly. Th is t o g e t h e r wit h A ( R; C[x2; xl¡2]) = ;
c o n t r a d ic t s Cla im 3 s in c e d+ ( xn¡2; R ) ¸ 1 a n d d¡ ( xl; R) ¸ 1 . A s s u m e , t h e r e fo r e , t h a t
d¡ ( x1; R ) ¸ 1 a n d d+ ( xl¡1; R) ¸ 1 . It fo llo ws t h a t y2x1 2 D s in c e y1x1 =2 D.

A s s u m e ¯ r s t t h a t yg = y2. Th e n xl¡1y1 2 D. S in c e y1xl¡1 =2 D, x1y2 =2 D a n d

d ( y1; C[x1; xl¡2]) = d( y2; C[x2; xl¡1]) = 0

u s in g L e m m a 3 .2 ( ii) we o b t a in t h a t

d( y1 ) = d ( y1; fy2g) + d( y1; C[xl¡1; xn¡2]) · n ¡ l + 2 a n d

d( y2 ) = d ( y2; fy1g ) + d ( y2; C[xl; x1]) · n ¡ l + 2 : ( 1 7 )
N o w we e xt e n d t h e p a t h P0 := C[xl; xn¡2] wit h t h e ve r t ic e s x1; x2; : : : ; xl¡1 a s m u c h a s
p o s s ib le . Th e n s o m e ve r t ic e s z1; z2; : : : ; zd 2 fx1; x2; : : : ; xl¡1g, d 2 [2 ; l ¡ 1 ], a r e n o t o n t h e
e xt e n d e d p a t h Pe s in c e o t h e r wis e Pe¡1 o r Pe t o g e t h e r wit h t h e a r c s xn¡2y1; y1y2 a n d y2xl
fo r m s a c yc le o f le n g t h n ¡ 1 . Th e r e fo r e , b y L e m m a 3 .2 , we h a ve t h a t d ( zi; C ) · n + d ¡ 3 .
If t h e r e is a zi =2 fx1; xl¡1g, t h e n d ( zi ) · n + d ¡ 3 a n d b y ( 1 7 ) ,

d ( zi ) + d ( y1 ) · 2 n ¡ 2 a n d d( zi ) + d( y2 ) · 2 n ¡ 2 ;

wh ic h c o n t r a d ic t s L e m m a 3 .5 s in c e zi is n o t a d ja c e n t t o y1 a n d y2. Th e r e fo r e , a s s u m e t h a t
fz1; z2g = fx1; xl¡1g ( d = 2 ) . Th e n Pe ( e = l ¡ 3 ¸ 1 ) is a n ( xl; xn¡2 ) -p a t h wit h ve r t e x
s e t V ( C ) ¡ fx1; xl¡1g. Th u s , we h a ve t h a t y2Pey1y2 is a c yc le o f le n g t h n ¡ 2 . Th e r e fo r e ,
b y Cla im 1 2 , x1xl¡1 2 D, a n d h e n c e , x1xl¡1Pe¡1y1y2x1 is a c yc le o f le n g t h n ¡ 1 , wh ic h
c o n t r a d ic t s t h e in it ia l 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 n ¡ 1 .

A s s u m e s e c o n d t h a t yg = y1. Th e n b y t h e a b o ve o b s e r va t io n we c o n c lu d e t h a t xl¡1y2 2
D a n d d( y1; C[x1; xl¡1]) = 0 . U s in g L e m m a 3 .2 , we o b t a in t h a t fo r t h is c a s e ( 1 7 ) a ls o
h o ld s , s in c e x1y2 =2 D a n d y2xl¡1 =2 D. A g a in we e xt e n d t h e p a t h C[xl; xn¡2] wit h ve r t ic e s
x1; x2; : : : ; xl¡1 a s m u c h a s p o s s ib le . Th e n s o m e ve r t ic e s z1; z2; : : : ; zd 2 fx1; x2; : : : ; xl¡1g,
d 2 [1 ; l ¡ 1 ], a r e n o t o n t h e e xt e n d e d p a t h Pe. S im ila r t o t h e ¯ r s t c a s e wh e n yg = y2, we will
o b t a in t h a t zi =2 fx2; x3; : : : ; xl¡2g ( i.e ., zi = x1 o r zi = xl¡1 ) a n d d( zi ) · n + d ¡ 2 . N o t ic e
t h a t C0 := y1Pey1 is a c yc le o f le n g t h n ¡ d ¡ 1 wit h ve r t e x s e t V ( C ) [ fy1g ¡ fz1; zdg. Fr o m
Cla im 1 2 it fo llo ws t h a t d = 2 , i.e ., fz1; zdg = fx1; xl¡1g ( s in c e x1y2 =2 D a n d yxl¡1 =2 D ) .
N o w fr o m l ¸ 4 , d = 2 , ( 1 7 ) a n d d ( zi ) · n + d ¡ 2 we o b t a in t h a t

d( y1 ) + d ( x1 ) · 2 n ¡ 2 a n d d ( y1 ) + d ( xl¡1 ) · 2 n ¡ 2 ;



S. Darbinyan and I. Karapetyan 2 1

wh ic h c o n t r a d ic t s L e m m a 3 .5 , s in c e y1; x1 a n d y1; xl¡1 a r e t wo d is t in c t p a ir s o f n o n a d ja c e n t
ve r t ic e s .

Case 14.2. A( R ! fx3; x4; : : : ; xn¡3g) = ;.
Th e n A( R ! fxn¡2; x1g ) 6= ; s in c e d¡ ( x2; R) = 0 a n d D is s t r o n g , a n d y1; xn¡3 a r e

n o n a d ja c e n t ( b y Cla im 1 3 ) . Fo r t h is c a s e we d is t in g u is h t h r e e s u b c a s e s .
Subcase 14.2.1. y2xn¡2 2 D.
Th e n , u s in g Cla im 1 3 , it is e a s y t o s e e t h a t xn¡3; y2 a r e n o n a d ja c e n t . Th e r e -

fo r e , d( xn¡3; R ) = 0 . Th is t o g e t h e r wit h y2xn¡2 2 D a n d Cla im 3 im p lie s t h a t
A ( fx1; x2; : : : ; xn¡3g ! R ) = ;. Th e r e fo r e , d( R; fx2; x3; : : : ; xn¡3g) = ; a n d d( y1 ) ,
d( y2 ) · 4 ( s in c e y2x1 =2 D b y Cla im 1 3 ) a n d d( xn¡3 ) · 2 n ¡ 6 . Fr o m t h is it fo llo ws
t h a t d( y1 ) + d ( xn¡3 ) · 2 n ¡ 2 a n d d( y2 ) + d ( xn¡3 ) · 2 n ¡ 2 , wh ic h c o n t r a d ic t s L e m m a 3 .5 .

Subcase 14.2.2. y2xn¡2 =2 D and y2x1 2 D.
Th e n u s in g Cla im 1 3 it is e a s y t o s e e t h a t y2 a n d xn¡2 a r e n o n a d ja c e n t .
L e t xn¡3y2 2 D. Th e n y1xn¡2 2 D ( b y Cla im 1 2 ) . U s in g Cla im s 1 2 a n d 1 3 we o b t a in

t h a t xn¡4 is n o t a d ja c e n t t o y1 a n d y2. S in c e d
¡ ( xn¡3; R ) = 0 a n d y1xn¡2 2 D, fr o m Cla im

3 ( i) it fo llo ws t h a t A( fx1; x2; : : : ; xn¡4g ! R) = ; a n d A( R; C[x2; xn¡4]) = ;. Th e r e fo r e a n d
d( y1 ) = d ( y2 ) = 4 a n d d ( x2 ) · 2 n ¡ 6 . Fr o m t h e s e it fo llo ws t h a t

d( y1 ) + d( x2 ) · 2 n ¡ 2 a n d d( y2 ) + d( x2 ) · 2 n ¡ 2 ;

wh ic h c o n t r a d ic t s L e m m a 3 .5 s in c e x2, y1 a n d x2; y2 a r e t wo d is t in c t p a ir s o f n o n a d ja c e n t
ve r t ic e s .

L e t n o w xn¡3y2 =2 D. Th e n y2; xn¡3 a r e n o n a d ja c e n t a n d h e n c e , d( xn¡3; R ) = 0 .
N o w, s in c e y1xn¡2 2 D o r d¡ ( xn¡2; R ) = 0 a n d y2x1 2 D, fr o m Cla im 3 it fo llo ws t h a t
A ( fx2; x3; : : : ; xn¡3g ! R ) = ;. Th e r e fo r e

d( y1; C[x1; xn¡3]) = d ( y2; C[x2; xn¡2]) = 0 ;

d( y1 ) · 4 , d( y2 ) · 4 a n d d( x2 ) · 2 n ¡ 6 . Th is c o n t r a d ic t s L e m m a 3 .5 s in c e x2, y1 a n d x2; y2
a r e t wo d is t in c t p a ir s o f n o n a d ja c e n t ve r t ic e s .

Subcase 14.2.3. y2xn¡2 =2 D and y2x1 =2 D.
Th e n y1xn¡2 2 D ( s in c e D is s t r o n g ) , t h e ve r t e x y1 is n o t a d ja c e n t t o t h e ve r t ic e s xn¡3,

xn¡4 a n d xn¡4y2 =2 D, i.e ., t h e ve r t ic e s y2; xn¡4 a ls o a r e n o n a d ja c e n t . U s in g Cla im 3 , we c a n
a s s u m e t h a t A ( C[x1; xn¡4] ! R ) = ;. Th e r e fo r e , d( y1 ) = 4 , d( y2 ) · 3 a n d d ( x1 ) · 2 n ¡ 6 .
Th is c o n t r a d ic t s L e m m a 3 .5 s in c e x1 is n o t a d ja c e n t t o y1 a n d y2. Th is c o m p le t e s t h e p r o o f
o f Cla im 1 4 .

Claim 15: If xiyf 2 D and the vertices yf ; xi+1 are nonadjacent, then the vertices
xi+1; y3¡f are adjacent, where i 2 [1 ; n ¡ 2 ] and f 2 [1 ; 2 ].

P r oof of Claim 15: 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 xi = xn¡2 ( i.e .,
xi+1 = x1 ) a n d yf = y1. S u p p o s e , o n t h e c o n t r a r y, t h a t x1; y2 a r e n o n a d ja c e n t . Fr o m
Cla im s 1 2 a n d 1 4 it fo llo ws t h a t y1x2 =2 D a n d x2y1 2 D. Th e r e fo r e , A ( R ! fx1; x2g ) = ;.
If n = 5 , t h e n x2y1; x3y1 2 D wh ic h c o n t r a d ic t s Cla im 1 3 . A s s u m e , t h e r e fo r e , t h a t n ¸
6 . A s D is s t r o n g , t h e r e is a ve r t e x xl wit h l 2 [3 ; n ¡ 2 ] s u c h t h a t d¡ ( xl; R ) ¸ 1 ( s a y
ygxl 2 D ) a n d A( R ! C[x1; xl¡1]) = ;. Th e n t h e ve r t ic e s xl¡1; yg a r e n o n a d ja c e n t a n d
d( xl¡2; R ) = 0 ( b y xl¡2y3¡g =2 D a n d b y Cla im 1 2 ) . N o w, s in c e xn¡2y1 a n d x2y1 2 D, t h e r e
e xis t s a ve r t e x xr 2 C[xn¡2; xl¡3] ( if l = 3 , t h e n xn¡2 = xl¡3 ) s u c h t h a t d+ ( xr; R) ¸ 1 a n d



2 2 On pre-Hamiltonian Cycles in Hamiltonian Digraphs

A( R; C[xr+1; xl¡2]) = ;. Th is c o n t r a d ic t s Cla im 3 s in c e d¡ ( xl¡1; R ) = 0 a n d d¡ ( xl; R ) ¸ 1 .
Cla im 1 5 is p r o ve d .

Claim 16: If xiyj 2 D, where i 2 [1 ; n ¡ 2 ] and j 2 [1 ; 2 ], then yjxi+2 2 D.
P r oof of Claim 16: 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 xi = xn¡2 a n d

yj = y1. 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 , t h a t is xn¡2y1 2 D a n d y1x2 =2 D. Th e n , b y
Cla im s 1 3 a n d 1 4 , t h e ve r t ic e s y1; x1 a r e n o n a d ja c e n t , x2y1 2 D ( h e n c e , n ¸ 6 ) a n d y1; x3
a r e a ls o n o n a d ja c e n t . Fr o m t h is , b y Cla im 1 5 we o b t a in t h a t t h e ve r t e x y2 is a d ja c e n t t o t h e
ve r t ic e s x1 a n d x3. Th e r e fo r e e it h e r y2x3 2 D o r x3y2 2 D.

Case 16.1. y2x3 2 D.
Th e n x2; y2 a r e n o n a d ja c e n t ( b y Cla im 1 3 ) , x2x1 2 D a n d x1y2 =2 D b y Cla im 1 2 ( fo r

o t h e r wis e D wo u ld h a ve a c yc le C0 o f le n g t h n ¡ 2 fo r wh ic h hV ( D ) ¡ V ( C0 ) i is n o t s t r o n g ) .
N o t ic e t h a t y2x1 2 D ( b y Cla im 1 5 ) . S in c e n e it h e r y1 n o r y2 c a n b e in s e r t e d in t o C, y1x2 =2 D
a n d y1; x1 a r e n o n a d ja c e n t ( r e s p e c t ive ly, x1y2 =2 D a n d y2; x2 a r e n o n a d ja c e n t ) u s in g L e m m a
3 .2 ( ii) , we o b t a in t h a t

d( y1 ) · n ¡ 1 a n d d( y2 ) · n ¡ 1 : ( 1 8 )
It is n o t d i± c u lt t o s e e t h a t xn¡2x2 =2 D a n d x1x3 =2 D ( fo r o t h e r wis e D c o n t a in s a c yc le
o f le n g t h n ¡ 1 ) . Th e r e fo r e , s in c e n e it h e r x1 n o r x2 c a n n o t b e in s e r t e d in t o C[x3; xn¡2]
( o t h e r wis e we o b t a in a c yc le o f le n g t h n ¡ 1 ) , a g a in u s in g L e m m a 3 .2 ( ii) , we o b t a in

d( x1 ) · n ¡ 1 a n d d( x2 ) · n ¡ 1 : ( 1 9 )

It is e a s y t o c h e c k t h a t n ¸ 7 .

Remar k: Observe that from (18), (19) and L emma 3.5 it follows that if xi 6= x1 and
y1; xi are nonadjacent or xi 6= x2 and xi; y2 are nonadjacent, then d ( xi ) ¸ n.

A s s u m e ¯ r s t t h a t d+ ( y1; C[x4; xn¡2]) ¸ 1 . L e t xl, l 2 [4 ; n ¡ 2 ], b e t h e ¯ r s t ve r t e x
a ft e r x3 t h a t y1xl 2 D. Th e n t h e ve r t ic e s y1 a n d xl¡1 a r e n o n a d ja c e n t . Th e r e fo r e , y1
a n d xl¡2 a r e a d ja c e n t ( b y Cla im 1 4 ) a n d h e n c e , xl¡2y1 2 D b e c a u s e o f x2y1 2 D a n d
m in im a lit y o f l ( l ¡ 1 6= 4 b y Cla im 1 4 , s in c e x2y1 2 D ) . S in c e xl¡1 c a n n o t b e in s e r t e d
in t o C[xl; xl¡2], u s in g L e m m a 3 .2 a n d t h e a b o ve R e m a r k, we o b t a in t h a t d( xl¡1 ) = n a n d
h e n c e , d ( y1 ) = n ¡ 1 ( b y L e m m a 3 .5 ) . Th is t o g e t h e r wit h d( y1; fx1; x2; x3; y2g ) = 3 im p lie s
t h a t d( y1; C[x4; xn¡2]) = n ¡ 4 . A g a in u s in g L e m m a 3 .2 , we o b t a in t h a t y1x4 2 D ( s in c e
jC[x4; xn¡2]j = n ¡ 5 ) . Th u s , y1C[x4; x2]y1 is a c yc le o f le n g t h n ¡ 2 . Th e r e fo r e , x3y2 2 D
( b y Cla im 1 2 ) , y1x5 =2 D a n d t h e ve r t ic e s y2; x4 a r e n o n a d ja c e n t ( b y Cla im 1 3 ) . Fr o m
y1x5 =2 D ( b y L e m m a 3 .2 ) we o b t a in t h a t d( y1; C[x5; xn¡2]) · n¡ 6 . Th e r e fo r e x4y1 2 D a n d
d( y1; C[x5; xn¡2]) = n ¡ 6 . N o w it is e a s y t o s e e t h a t y1; x5 a r e n o n a d ja c e n t ( b y Cla im 1 3 )
a n d y2; x5 a r e a d ja c e n t ( b y Cla im 1 4 ) . Th e r e fo r e , d( y1; C[x6; xn¡2]) = n ¡ 6 a n d y1x6 2 D
( b y L e m m a 3 .2 ) , y2x5; x5y2 2 D ( b y Cla im 1 2 ) , y1x7 =2 D ( b y Cla im 1 3 ) . On e r e a d ily s e e s
t h a t , b y c o n t in u in g t h e a b o ve p r o c e d u r e , we e ve n t u a lly o b t a in t h a t n is e ve n a n d

N ¡ ( y1 ) = fy2; x2; x4; x6; : : : ; xn¡2g; N + ( y1 ) = fy2; x4; x6; : : : ; xn¡2g;

N ¡ ( y2 ) = fy1; x3; x5; : : : ; xn¡3g; N + ( y2 ) = fy1; x1; x3; x5; : : : ; xn¡3g:
Fr o m Cla im 1 2 it fo llo ws t h a t xixi¡1 2 D fo r a ll i 2 [4 ; n ¡ 2 ] a n d x2x1 2 D. It is e a s y t o
s e e t h a t x1x3 =2 D a n d x3x5 =2 D. Th e r e fo r e , s in c e x3 c a n n o t b e in s e r t e d in t o C[x5; x1], b y
L e m m a 3 .2 , we h a ve d ( x3; C[x5; x1]) · n ¡ 6 . Th is t o g e t h e r wit h d( x3 ) ¸ n ( b y R e m a r k)



S. Darbinyan and I. Karapetyan 2 3

im p lie s t h a t d( x3; fx2; x4; y2g ) = 6 . In p a r t ic u la r , x3x2 2 D. N o w we c o n s id e r t h e ve r t e x
xn¡2. N o t e t h a t d( xn¡2 ) ¸ n ( b y R e m a r k) , xn¡2x2 =2 D a n d xn¡4xn¡2 =2 D. Fr o m t h is it
is n o t d i± c u lt t o s e e t h a t d( xn¡2; C[x2; xn¡4]) · n ¡ 6 a n d x1xn¡2 2 D. It fo llo ws t h a t
xn¡2xn¡3 : : : x4x3y2x1xn¡2 is a c yc le o f le n g t h n ¡ 2 , wh ic h d o e s n o t c o n t a in t h e ve r t ic e s y1
a n d x2. Th is c o n t r a d ic t s Cla im 1 2 , s in c e y1x2 =2 D ( b y o u r s u p p o s it io n ) , i.e ., hfy1; x2gi is
n o t s t r o n g .

A s s u m e n e xt t h a t d+ ( y1; C[x4; xn¡2]) = 0 . Th e n fr o m Cla im s 1 3 a n d 1 4 it fo llo ws t h a t

N ¡ ( y1 ) = fy2; x2; x4; : : : ; xn¡2g a n d N + ( y1 ) = fy2g: ( 2 0 )

B y Cla im 1 5 we h a ve t h a t t h e ve r t e x y2 is a d ja c e n t t o e a c h ve r t e x xi 2 fx1; x3; : : : ; xn¡3g.
It is e a s y t o s e e t h a t xn¡3y2 =2 D a n d h e n c e , y2xn¡3 2 D ( fo r o t h e r wis e if xn¡3y2 2 D, t h e n
y2C[x1; xn¡3]y2 is a c yc le o f le n g t h n ¡ 2 , b u t hfxn¡2; y1gi is n o t s t r o n g , a c o n t r a d ic t io n t o
Cla im 1 2 ) . B y a n a r g u m e n t s im ila r t o t h a t in t h e p r o o f o f ( 2 0 ) we d e d u c e t h a t

N + ( y2 ) = fy1; x1; x3; : : : ; xn¡3g a n d N¡ ( y2 ) = fy1g:

Th u s we h a ve t h a t y1y2C[x5; x2]y1 is a c yc le o f le n g t h n ¡ 2 a n d x3 c a n n o t b e in s e r t e d in t o
C[x5; x2]. Th e r e fo r e , b y L e m m a 3 .2 ( ii) , d( x3; C[x5; x2]) · n ¡ 4 s in c e x3x5 =2 D. Th is t o -
g e t h e r wit h d( x3; fx4; y1; y2g ) · 3 im p lie s t h a t d ( x3 ) · n ¡ 1 wh ic h c o n t r a d ic t s t h e a b o ve
R e m a r k t h a t d ( x3 ) ¸ n.

Case 16.2. y2x3 =2 D.
Th e n , a s n o t e d a b o ve , x3y2 2 D. Th e r e fo r e d ( y2; fx2; x4g ) = 0 ( b y Cla im 1 3 a n d y2x2 =2

D ) , y1x4 =2 D ( b y Cla im 1 2 ) , x4y1 2 D ( b y Cla im 1 5 ) , t h e ve r t ic e s x5; y1 a r e n o n a d ja c e n t
a n d t h e ve r t ic e s y2; x5 a r e a d ja c e n t ( b y Cla im 1 5 ) . S in c e x3y2 2 D, y1x4 =2 D a n d y2; x5 a r e
a d ja c e n t , fr o m Cla im 1 2 it fo llo ws t h a t y2x5 =2 D a n d x5y2 2 D. Fo r t h e s a m e r e a s o n , we
d e d u c e t h a t

N¡ ( y1 ) = fy2; x2; x4; : : : ; xn¡2g N¡ ( y2 ) = fy1; x1; x3; : : : ; xn¡3g a n d A ( R ! 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 . 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 1 6 .

W e will n o w c o m p le t e t h e p r o o f o f Th e o r e m b y s h o win g t h a t D is is o m o r p h ic t o K¤n=2;n=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 xn¡2y1 2 D. Th e n u s in g Cla im s 1 2 , 1 3 , 1 4 a n d
1 6 we c o n c lu d e t h a t y1; x1 a r e n o n a d ja c e n t ( Cla im 1 3 ) , y1x2 2 D ( Cla im 1 6 ) , x1y2; y2x1 2 D
( Cla im 1 2 ) , x2; y2 a ls o a r e n o n a d ja c e n t ( Cla im 1 3 ) , y2x3 2 D ( Cla im 1 6 ) a n d x2y1 2 D
( Cla im 1 2 ) . B y c o n t in u in g t h is p r o c e d u r e , we e ve n t u a lly o b t a in t h a t n is e ve n a n d

N + ( y1 ) = N
¡ ( y1 ) = fy2; x2; x4; : : : ; xn¡2g a n d N + ( y2 ) = N¡ ( y2 ) = fy1; x1; x3; : : : ; xn¡3g:

If xixj 2 D fo r s o m e xi; xj 2 fx1; x3; : : : ; xn¡3g, t h e n c le a r ly jC[xi; xj ]j ¸ 5 a n d
xixjxj+1 : : : xi¡1y1xi+1 : : : xj¡2y2xi is a c yc le o f le n g t h n ¡ 1 , c o n t r a r y t o o u r a s s u m p t io n .
Th e r e fo r e , fy1; x1; x3; : : : ; xn¡3g is a n in d e p e n d e n t s e t o f ve r t ic e s . Fo r t h e s a m e r e a s o n
fy2; x2; x4; : : : ; xn¡2g a ls o 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 w fr o m t h e c o n d it io n A0
it fo llo ws t h a t D is is o m o r p h ic t o K¤n=2;n=2. Th is c o m p le t e s t h e p r o o f o f Th e o r e m 1 .1 0 .



2 4 On pre-Hamiltonian Cycles in Hamiltonian Digraphs

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

A H a m ilt o n ia n b yp a s s in a d ig r a p h is a s u b d ig r a p h o b t a in e d fr o m a H a m ilt o n ia n c yc le o f D
b y r e ve r s in g o n e a r c .

U s in g Th e o r e m 1 .1 0 , t h e ¯ r s t a u t h o r h a s p r o ve d t h a t if a s t r o n g d ig r a p h D o f o r d e r n ¸ 4
s a t is ¯ e s t h e c o n d it io n A0, t h e n D c o n t a in s a H a m ilt o n ia n b yp a s s o r D is is o m o r p h ic t o o n e
t o u r n a m e n t o f o r d e r 5 .

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

[2 ] J. B a n g -Je n s e n , G. Gu t in a n d H . L i, \ S u ± c ie n t c o n d it io n s fo r a d ig r a p h t o b e H a m il-
t o n ia n " , J ournal of Graph Theory, vo l. 2 2 , n o . 2 , p p . 1 8 1 -1 8 7 , 1 9 9 6 .

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

[4 ] J. A . B o n d y, \ B a s ic g r a p h t h e o r y: p a t h s a n d c ir c u it s " , In Handbook of combinatorics,
vo l. 1 , n o . 2 , E ls e vie r , A m s t e r d a m , 1 9 9 5 .

[5 ] J. A . B o n d y a n d C. Th o m a s s e n , \ A s h o r t p r o o f o f Me yn ie l's t h e o r e m " , D iscrete M ath-
ematics, vo l. 1 9 , n o . 1 , p p . 1 9 5 -1 9 7 , 1 9 7 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 . Thesis, Institute
M athematici Akademy Nauk B SSR , M insk, 1981 ( 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 , Studia Scientiarum M athematicarum Hungarica, ( in R u s s ia n ) ,
vo l.2 0 , n o . 1 -4 , 9 5 -1 1 7 , 1 9 8 5 .)

[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 " , Akademy Nauk Armyan. SSR D oklady, 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 ] 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 " , Akademy
Nauk Armyan. SSR D oklady, vo l. 8 3 , n o .4 , 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 ) .

[9 ] S .K h . D a r b in ya n a n d I.A . K a r a p e t ya n , \ On lo n g e s t n o n -H a m ilt o n ia n c yc le s in d ig r a p h s
wit h t h e c o n d it io n s o f B a n g -Je n s e n , Gu t in a n d L i" , P reprint available at htte: arXiv
1207.5643v2 [math.CO], 2 0 S e p 2 0 1 2 .

[1 0 ] S . K h . D a r b in ya n a n d I.A . K a r a p e t ya n , \ A n o t e o n lo n g n o n -H a m ilt o n ia n c yc le s in o n e
c la s s o f d ig r a p h s " , P reprint available at htte: arXiv 1209.4456v1 [math.CO], 2 0 S e p
2 0 1 2 .

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

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

[1 3 ] G. Gu t in , \ Ch a r a c t e r iz a t io n s o f ve r t e x p a n c yc lic a n d p a n c yc lic o r d in a r y c o m p le t e m u l-
t ip a r t it e d ig r a p h s " , D iscrete M athematics, vo l.1 4 1 , p p . 1 5 3 -1 6 2 , 1 9 9 5 .

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



S. Darbinyan and I. Karapetyan 2 5

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

[1 6 ] 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 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 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 .

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

Submitted 16.10.2014, accepted 27.01.2015.

ÎáÕÙÝáñáßí³Í ѳÙÇÉïáÝÛ³Ý ·ñ³ýÝ»ñÇ Ý³Ë³Ñ³ÙÇÉïáÝÛ³Ý
óÇÏÉ»ñÇ Ù³ëÇÝ

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

²Ù÷á÷áõÙ

ÎáÕÙÝáñáßí³Í ·ñ³ýÇ ÏáÕÙÝáñáßí³Í óÇÏÉÁ, áñÝ ³ÝóÝáõÙ ¿ Ýñ³ µáÉáñ ·³·³ÃÝ»ñáí,
µ³óÇ Ù»ÏÇó, ÏáãíáõÙ ¿ ݳ˳ѳÙÇÉïáÝÛ³Ý óÇÏÉ: Ü»ñϳ ³ß˳ï³ÝùáõÙ ³å³óáõóí³Í
¿, áñ »Ã» ÏáÕÙÝáñáßí³Í ·ñ³ýÁ µ³í³ñ³ñáõÙ ¿ سÝááõë³ÏÇëÇ Ñ³ÙÇÉïÝÛ³ÝáõÃÛ³Ý
µ³í³ñ³ñ å³ÛÙ³ÝÇÝ (J. of Graph Theory 16(1) (1992) 51-59), ³å³ ³ÛÝ å³ñáõݳÏáõÙ
¿ ݳ˳ѳÙÇÉïáÝÛ³Ý óÇÏÉ, µ³óÇ ³ÛÝ ¹»åùÇó, »ñµ ³Û¹ ·ñ³ýÁ ǽáÙáñý ¿ »ñÏÙ³ë
ѳí³ë³ñ³Ïßéí³Í ÏáÕÙÝáñáßí³Í ÉñÇí ·ñ³ýÇÝ:

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

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

Àííîòàöèÿ

Îðèåíòèðîâàííûé êîíòóð, êîòîðûé ñîäåðæèò âñå âåðøèíû îðèåíòèðîâàííîãî
ãðàôà (îðãðàôà), íàçûâàåòñÿ ïðåäãàìèëüòîíîâûì êîíòóðîì. Â ðàáîòå
äîêàçàíî, ÷òî ëþáîé îðãðàô, êîòîðûé óäîâëåòâîðÿåò äîñòàòî÷íîìó óñëîâèþ
ãàìèëüòîíîâîñòè îðãðàôîâ Ìàíîóñàêèñà (J. of Graph Theory 16(1) (1992) 51-59),
ñîäåðæèò ïðåäãàìèëüòîíîâûé êîíòóð èëè ÿâëÿåòñÿ äâóäîëüíûì áàëàíñèðîâàííûì
ïîëíûì îðãðàôîì.