Zhora_Nikoghosyan2.DVI


Mathematical Problems of Computer Science 46, 44{49, 2016.

A Common Gener alization of Dir ac's Two T heor ems

Ca r le n M. Mo s e s ya n 1 a n d Zh o r a G. N iko g h o s ya n 2;¤

1 Kh. Abovyan Armenian State University
2 Institute for Informatics and Automation Problems of NAS RA

e-mail: mosesyan@list.ru, zhora@ipia.sci.am

Abstract

A theorem is proved including Dirac's two well-known theorems (1952) as particular
cases.

Keywords: Hamilton cycle, Longest cycle, Longest path, Minimum degree.

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

W e c o n s id e r o n ly u n d ir e c t e d g r a p h s wit h n o lo o p s o r m u lt ip le e d g e s . Fo r a g r a p h G, we u s e n
a n d c t o d e n o t e t h e o r d e r a n d t h e c ir c u m fe r e n c e ( t h e o r d e r o f a lo n g e s t c yc le ) o f G. A g r a p h
G is h a m ilt o n ia n if G c o n t a in s a H a m ilt o n c yc le , t h a t is a s im p le c yc le C wit h jCj = c = n.
A g o o d r e fe r e n c e fo r a n y u n d e ¯ n e d t e r m s is [1 ].

Th e e a r lie s t t wo n o n t r ivia l lo we r b o u n d s fo r t h e c ir c u m fe r e n c e we r e d e ve lo p e d in 1 9 5 2
d u e t o D ir a c [2 ] in t e r m s o f m in im u m d e g r e e ± a n d p - t h e o r d e r o f a lo n g e s t p a t h in G,
r e s p e c t ive ly.
T heor em A: [2 ]. If G is a 2-connected graph, then c ¸ m in fn; 2 ±g.
T heor em B : [2 ]. If G is a 2-connected graph, then c ¸

p
2 p.

In t h is p a p e r we p r e s e n t a c o m m o n g e n e r a liz a t io n o f Th e o r e m A a n d Th e o r e m B , in c lu d -
in g b o t h ± a n d p in a c o m m o n r e la t io n a s p a r a m e t e r s .
T heor em 1: If G is a 2-connected graph, then

c ¸

8
>>>>>><
>>>>>>:

p; wh e n p · 2 ±;

p ¡ 1 ; wh e n 2 ± + 1 · p · 3 ± ¡ 2 ;
q

2 p ¡ 1 0 + ( ± ¡ 7
2
) 2 + ± + 1

2
; wh e n p ¸ 3 ± ¡ 1 :

S in c e G is 2 -c o n n e c t e d , we h a ve n ¸ 3 . If p · 2 ±, t h e n b y Th e o r e m 1 , c ¸ p, im p lyin g
t h a t c = p = n ( G is h a m ilt o n ia n ) a n d c = p >

p
2 p. N e xt , if 2 ± + 1 · p · 3 ± ¡ 2 , t h e n b y

Th e o r e m 1 , c ¸ p ¡ 1 . S in c e p ¸ 2 ± + 1 ¸ 5 , we h a ve c ¸ p ¡ 1 ¸ 2 ± a n d c ¸ p ¡ 1 >
p

2 p.
Fin a lly, if p ¸ 3 ± ¡ 1 , t h e n

s

2 p ¡ 1 0 +
µ
± ¡ 7

2

¶2
¸

s

2 ( 3 ± ¡ 1 ) ¡ 1 0 +
µ
± ¡ 7

2

¶2
= ± ¡ 1

2
;

¤G.G. Nicoghossian (up to 1997)

4 4



C. Mosesyan and Zh. Nikoghosyan 4 5

im p lyin g t h a t c ¸ 2 ± ( b y Th e o r e m 1 ) a n d
µ
± +

1

2

¶ s

2 p ¡ 1 0 +
µ
± ¡ 7

2

¶2
+ ±2 ¡ 3 ± + 5

4

¸
µ
± +

1

2

¶ µ
± ¡ 1

2

¶
+ ±2 ¡ 3 ± + 5

4
= ( ± ¡ 1 ) ( 2 ± ¡ 1 ) > 0 :

Ob s e r vin g t h a t t h e in e qu a lit y

µ
± +

1

2

¶ s

2 p ¡ 1 0 +
µ
± ¡ 7

2

¶2
+ ±2 ¡ 3 ± + 5

4
> 0

is e qu iva le n t t o s

2 p ¡ 1 0 +
µ
± ¡ 7

2

¶2
+ ± +

1

2
>

q
2 p;

we c o n c lu d e ( b y Th e o r e m 1 ) t h a t c >
p

2 p.
Th u s , Th e o r e m 1 yie ld s Th e o r e m A a n d is s t r o n g e r t h a n Th e o r e m B .
To s h o w t h a t Th e o r e m 1 is b e s t p o s s ib le in a s e n s e , o b s e r ve ¯ r s t t h a t in g e n e r a l, p ¸ c,

t h a t is c = p wh e n p · 2 ±, im p lyin g t h a t t h e b o u n d c ¸ p in Th e o r e m 1 c a n n o t b e r e p la c e d
b y c ¸ p + 1 . On t h e o t h e r h a n d , t h e g r a p h K±;±+1, wh e r e p = 2 ± + 1 a n d c = 2 ± = p ¡ 1
s h o ws t h a t t h e c o n d it io n p · 2 ± c a n n o t b e r e la xe d t o p · 2 ± + 1 . In a d d it io n , t h e g r a p h
K±;±+1, wh e r e c = p, s h o ws t h a t t h e b o u n d c ¸ p ¡ 1 ( wh e n 2 ± + 1 · p · 3 ± ¡ 2 ) c a n n o t b e
r e p la c e d b y c ¸ p. Fu r t h e r , t h e g r a p h K2 + 3 K±¡1, wh e r e n = p = 3 ± ¡ 1 a n d c = 2 ± · p ¡ 2
s h o ws t h a t t h e c o n d it io n p · 3 ± ¡ 2 c a n n o t b e r e la xe d t o p · 3 ± ¡ 1 . Fin a lly, t h e s a m e
g r a p h K2 + 3 K±¡1, wh e r e p = 3 ± ¡ 1 a n d

c = 2 ± =

s

2 p ¡ 1 0 +
µ
± ¡ 7

2

¶2
+ ± +

1

2
;

s h o ws t h a t t h e b o u n d
q

2 p ¡ 1 0 + ( ± ¡ 7
2
) 2 + ± + 1

2
in Th e o r e m 1 c a n n o t b e im p r o ve d t o

q
2 p ¡ 1 0 + ( ± ¡ 7

2
) 2 + ± + 1 .

Fo r a s p e c ia l c a s e wh e n 2 ± + 1 · p · 3 ± ¡ 2 , we u s e t h e r e s u lt o f Oz e ki a n d Y a m a s h it a
[3 ].
T heor em C: [3 ]. L et G be a 2-connected graph. Then either

( i ) c ¸ p ¡ 1 o r
( ii) c ¸ 3 ± ¡ 3 o r
( iii ) · = 2 a n d p ¸ 3 ± ¡ 1 .

2 . N o t a t io n a n d P r e lim in a r ie s

Th e s e t o f ve r t ic e s o f a g r a p h G is d e n o t e d b y V ( G ) a n d t h e s e t o f e d g e s - b y E ( G ) . Th e
n e ig h b o r h o o d o f a ve r t e x x 2 V ( G ) will b e d e n o t e d b y N ( x ) . W e u s e d( x ) t o d e n o t e jN ( x ) j.

P a t h s a n d c yc le s in a g r a p h G a r e c o n s id e r e d a s s u b g r a p h s o f G. If Q is a p a t h o r a c yc le ,
t h e n t h e o r d e r o f Q, d e n o t e d b y jQj, is jV ( Q ) j. W e wr it e a c yc le Q wit h a g ive n o r ie n t a t io n
b y

¡!
Q . Fo r x; y 2 V ( Q ) , we d e n o t e b y x¡!Q y t h e s u b p a t h o f Q in t h e c h o s e n d ir e c t io n fr o m

x t o y. Fo r x 2 V ( Q) , we d e n o t e t h e h-t h s u c c e s s o r a n d t h e h-t h p r e d e c e s s o r o f x o n ¡!Q
b y x+h a n d x¡h, r e s p e c t ive ly. W e a b b r e via t e x+1 a n d x¡1 b y x+ a n d x¡, r e s p e c t ive ly. Fo r



4 6 A Common Generalization of Dirac's Two Theorems

U µ V ( Q ) , U + = fu+ju 2 Ug a n d U ¡ = fu¡ju 2 Ug. W e s a y t h a t ve r t e x z1 p r e c e d e s ve r t e x
z2 o n

¡!
Q if z1, z2 o c c u r o n

¡!
Q in t h is o r d e r , a n d in d ic a t e t h is r e la t io n s h ip b y z1 Á z2. W e

will wr it e z1 ¹ z2 wh e n e it h e r z1 = z2 o r z1 Á z2.
L e t P = x

¡!
P y b e a p a t h . A vin e o n P is a s e t

fLi = xi
¡!
L iyi : 1 · i · mg

o f in t e r n a lly-d is jo in t p a t h s s u c h t h a t

( a ) V ( Li ) \ V ( P ) = fxi; yig ( i = 1 ; :::; m) ,
( b ) x = x1 Á x2 Á y1 ¹ x3 Á y2 ¹ x4 Á ::: ¹ xm Á ym¡1 Á ym = y o n P .

T he Vine Lemma: [4 ]. L et G be a k-connected graph and P a path in G. Then there are
k ¡ 1 pairwise-disjoint vines on P .

Th e n e xt t h r e e le m m a s a r e c r u c ia l fo r t h e p r o o f o f Th e o r e m 1 .

Lemma 1: L et G be a connected graph and P = x
¡!
P y a longest path in G.

( i ) If xz; yz¡ 2 E ( G ) for some z 2 V ( x+¡!P y ) , then c = p = n, that is G is hamiltonian.
( ii) If d( x ) + d( y ) ¸ p, then c = p = n.
( iii ) L et yz1; xz2 2 E ( G ) for some z1; z2 2 V ( P ) with x Á z1 Á z2 Á y and jz1

¡!
P z2j ¸ 3 .

If xz; yz 62 E ( G) for each z 2 V ( z+1
¡!
P z¡2 ) and d ( x) + d ( y ) ¸ p + 3 ¡ jz1

¡!
P z2j, then c = p.

Lemma 2: L et G be a 2-connected graph and fL1; L2; :::; Lmg be a vine on a longest path of
G. Then

c ¸ 2 p ¡ 1 0
m + 1

+ 4 :

Lemma 3: L et G be a connected graph and fL1; L2; :::; Lmg be a vine on a longest path
P = x

¡!
P y of G. Then either c = p or c ¸ d( x ) + d( y ) + m ¡ 2 .

3 . P r o o fs

P r oof of Lemma 1: ( i ) L e t xz; yz¡ 2 E ( G ) fo r s o m e z 2 V ( x+¡!P y ) . Th e n c ¸
jxz¡!P yz¡Ã¡P xj = p. If V ( G) = V ( P ) , t h e n c le a r ly c = p. Ot h e r wis e , r e c a llin g t h a t G is
c o n n e c t e d , we c a n fo r m a p a t h lo n g e r t h a t P , a c o n t r a d ic t io n .

( ii) L e t d( x ) + d( y ) ¸ p. If xz; yz¡ 2 E ( G) fo r s o m e z 2 V ( x+¡!P y ) , t h e n we c a n a r g u e
a s in ( i) . Ot h e r wis e N ( x ) \ N + ( y ) = ;. Ob s e r vin g a ls o t h a t x 62 N ( x) [ N + ( y ) , we g e t

p ¸ jN ( x ) j + jN + ( y ) j + jfx1gj

= jN ( x) j + jN ( y ) j + 1 = d( x ) + d( y ) + 1 ;
c o n t r a d ic t in g t h e h yp o t h e s is .

( iii ) A s s u m e t h e c o n t r a r y, t h a t is c · p ¡ 1 . Th e n b y ( i ) , N ( x ) \ N + ( y ) = ;. Cle a r ly,
x 62 N ( x) [ N + ( y ) . Fu r t h e r , b y t h e h yp o t h e s is ,

V ( z+21
¡!
P z¡2 ) \ ( N ( x ) [ N + ( y ) ) = ;;

im p lyin g t h a t

p ¸ jfxgj + jN ( x) j + jN + ( y ) j + jV ( z+21
¡!
P z¡2 ) j



C. Mosesyan and Zh. Nikoghosyan 4 7

= d( x ) + d( y ) + jz1
¡!
P z2j ¡ 2 ;

c o n t r a d ic t in g t h e h yp o t h e s is . Th u s , c = p. L e m m a 1 is p r o ve d .

P r oof of Lemma 2: L e t P = x
¡!
P y b e a lo n g e s t p a t h in G. P u t

Li = xi
¡!
L iyi ( i = 1 ; :::; m) ; A1 = x1

¡!
P x2; Am = ym¡1

¡!
P ym;

Ai = yi¡1
¡!
P xi+1 ( i = 2 ; 3 ; :::; m ¡ 1 ) ; Bi = xi+1

¡!
P yi ( i = 1 ; :::; m ¡ 1 ) ;

jAij ¡ 1 = ai ( i = 1 ; :::; m ) ; jBij ¡ 1 = bi ( i = 1 ; :::; m ¡ 1 ) :
B y c o m b in in g a p p r o p r ia t e Li; Ai; Bi, we c a n fo r m t h e fo llo win g c yc le s :

Q1 =
m[

i=1

Ai [
m[

i=1

Li;

Q2 =
m¡1[

i=1

Ai [ Bm¡1 [
m¡1[

i=1

Li;

Q3 =
m[

i=2

Ai [ B1 [
m[

i=2

Li;

Ri = Bi [ Ai+1 [ Bi+1 [ Li+1 ( i = 1 ; :::; m ¡ 2 ) :
S in c e jLij ¸ 2 ( i = 1 ; :::; m ) , we h a ve

c ¸ jQ1j =
mX

i=1

ai +
mX

i=1

( jLij ¡ 1 ) ¸
mX

i=1

ai + m;

c ¸ jQ2j = bm¡1 +
m¡1X

i=1

ai +
m¡1X

i=1

( jLij ¡ 1 ) ¸ bm¡1 +
m¡1X

i=1

ai + m ¡ 1 ;

c ¸ jQ3j = b1 +
mX

i=2

ai +
mX

i=2

( jLij ¡ 1 ) ¸ b1 +
mX

i=2

ai + m ¡ 1 ;

c ¸ jRij = bi + ai+1 + bi+1 + jLi+1j ¡ 1
¸ bi + ai+1 + bi+1 + 1 ( i = 1 ; :::; m ¡ 2 ) :

B y s u m m in g , we g e t

( m + 1 ) c ¸
Ã

2
mX

i=1

ai + 2
m¡1X

i=1

bi

!
+ 2

m¡1X

i=2

ai + 4 m ¡ 4

¸ 2
Ã

mX

i=1

ai +
m¡1X

i=1

bi + 1

!
+ 4 m ¡ 6 = 2 p + 4 m ¡ 6 ;

im p lyin g t h a t

c ¸ 2 p ¡ 1 0
m + 1

+ 4 :

L e m m a 2 is p r o ve d .
P r oof of Lemma 3: If m = 1 , t h e n xy 2 E ( G ) a n d b y L e m m a 1 ( i ) , c = p. L e t m ¸ 2 .
P u t Li = xi

¡!
L iyi ( i = 1 ; :::; m ) a n d le t

Ai; Bi; ai; bi; Qi



4 8 A Common Generalization of Dirac's two Theorems

b e a s d e ¯ n e d in t h e p r o o f o f L e m m a 2 .
Case 1: m = 2 .

A s s u m e wit h o u t lo s s o f g e n e r a lit y t h a t L1 a n d L2 a r e c h o s e n s o a s t o m in im iz e b1. Th is
m e a n s t h a t N ( x ) [ N ( y ) µ V ( A1 [ A2 ) . B y L e m m a 1 ( iii ) , e it h e r c = p o r d( x ) + d( y ) ·
p + 2 ¡ jz1

¡!
P z2j = p + 1 ¡ b1. If c = p, t h e n we a r e d o n e . L e t d ( x) + d( y ) · p + 1 ¡ b1, t h a t

is p ¸ d ( x) + d( y ) + b1 ¡ 1 . Th e n p = a1 + a2 + b1 + 1 ¸ d ( x) + d ( y ) + b1 ¡ 1 , im p lyin g t h a t
c ¸ jQ1j = a1 + a2 + 2 ¸ d( x ) + d ( y ) = d( x ) + d( y ) + m ¡ 2 :

Case 2: m = 3 .
L e t xz1; yz2 2 E ( G ) fo r s o m e z1; z2 2 V ( P ) . If z2 Á z1 t h e n fxz1; yz2g is a vin e c o n s is t in g

o f t wo p a t h s ( e d g e s ) a n d we c a n a r g u e a s in Ca s e 1 . Ot h e r wis e we h a ve

N ( x ) µ V ( A1 [ A2 ) ; N ( y ) µ V ( A2 [ A3 )
a n d z1 ¹ z2 fo r e a c h z1 2 N ( x) a n d z2 2 N ( y ) . Th e r e fo r e , a1 + a2 + a3 ¸ d( x ) + d( y ) ¡ 2 a n d

c ¸ jQ1j = a1 + a2 + a3 + 3
¸ d( x ) + d( y ) + 1 = d( x ) + d( y ) + m ¡ 2 :

Case 3: m ¸ 4 .
Ch o o s e fL1; :::; Lmg s o a s t o m in im iz e m. Th e n c le a r ly

N ( x ) µ V ( A1 [ A2 ) ; N ( y ) µ V ( Am¡1 [ Am )
a n d z1 Á z2 fo r e a c h z1 2 N ( x ) a n d z2 2 N ( y ) . Ob s e r vin g a ls o t h a t

a1 + a2 ¸ d( x ) ¡ 1 ; am¡1 + am ¸ d( y ) ¡ 1 ;
we g e t

c ¸ jQ1j =
mX

i=1

ai + m = ( a1 + a2 + am¡1 + am ) +
m¡2X

i=3

ai + m

¸ d ( x ) + d( y ) ¡ 2 +
m¡2X

i=3

ai + m ¸ d ( x) + d ( y ) + m ¡ 2 :

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

P r oof of T heor em 1: L e t P = x
¡!
P y b e a lo n g e s t p a t h in G.

Case 1: p · 2 ±.
If xy 2 E ( G) , t h e n b y L e m m a 1 ( i) , c = p. L e t xy 62 E ( G) . Th e n d( x ) + d ( y ) ¸ 2 ± ¸ p

a n d b y L e m m a 1 ( ii) , c = p.
Case 2: 2 ± + 1 · p · 3 ± ¡ 2 .

If c ¸ 3 ± ¡ 3 , t h e n c ¸ p + 2 ¡ 3 = p ¡ 1 . N e xt , if · = 2 a n d p ¸ 3 ± ¡ 1 , t h e n
p ¸ 3 ± ¡ 1 ¸ p + 1 , a c o n t r a d ic t io n . B y Th e o r e m C, c ¸ p ¡ 1 .
Case 3: p ¸ 3 ± ¡ 1 .

S in c e G is 2 -c o n n e c t e d , t h e r e is a vin e fL1; :::; Lmg o n P . B y L e m m a 3 , m · c ¡ d ( x) ¡
d( y ) + 2 · c ¡ 2 ± + 2 . U s in g L e m m a 2 , we g e t

c ¸ 2 p ¡ 1 0
m + 1

+ 4 ¸ 2 p ¡ 1 0
c ¡ 2 ± + 3 + 4 ;

im p lyin g t h a t

c ¸
s

2 p ¡ 1 0 +
µ
± ¡ 7

2

¶2
+ ± +

1

2
:

Th e o r e m 1 is p r o ve d .



C. Mosesyan and Zh. Nikoghosyan 4 9

Refer ences

[1 ] J. A . B o n d y a n d U . S . R . Mu r t y, Graph Theory with Applications, Ma c m illa n , L o n d o n
a n d E ls e vie r , N e w Y o r k, 1 9 7 6 .

[2 ] G. A . D ir a c , \ S o m e t h e o r e m s o n a b s t r a c t g r a p h s " , P roc. L ondon, M ath. Soc., vo l. 2 ,
p p . 6 9 -8 1 , 1 9 5 2 .

[3 ] K . Oz e ki a n d T. Y a m a s h it a , \ L e n g t h o f lo n g e s t c yc le s in a g r a p h wh o s e r e la t ive le n g t h
is a t le a s t t wo " , Graphs and Combinatorics, vo l. 2 8 , p p . 8 5 9 -8 6 8 , 2 0 1 2 .

[4 ] J. A . B o n d y, B asic Graph Theory: P aths and circuits, H a n d b o o k o f Co m b in a t o r ic s ,
E ls e vie r , A m s t e r d a m , vo l. 1 ,2 , 1 9 9 0 .

Submitted 01.07.2016, accepted 02.11.2016.

¸Çñ³ÏÇ »ñÏáõ ûáñ»ÙÝ»ñÇ ÁݹѳÝñ³óáõÙ

Î. Øáë»ëÛ³Ý ¨ Ä. ÜÇÏáÕáëÛ³Ý

²Ù÷á÷áõÙ

²å³óáõóíáõÙ ¿ ÙÇ Ã»áñ»Ù, áñÝ Áݹ·ñÏáõÙ ¿ 1952-ÇÝ ¸Çñ³ÏÇ ÏáÕÙÇó ëï³óí³Í »ñÏáõ
ѳÛïÝÇ Ã»áñ»ÙÝ»ñÁ áñå»ë Ù³ëݳíáñ ¹»åù»ñ:

Îáîáùåíèå äâóõ òåîðåì Äèðàêà
Ê. Ìîñåñÿí è Æ. Íèêîãîñÿàí

Àííîòàöèÿ

Äîêàçûâàåòñÿ îäíà òåîðåìà, êîòîðàÿ âêëþ÷àåò äâå èçâåñòíûå òåîðåìû
Äèðàêà, ïîëó÷åííûå â 1952 ã., êàê ÷àñòíûå ñëó÷àè.