2_nikoghosyan_14--18.DVI


Mathematical Problems of Computer Science 48, 14{18, 2017.

N ew E xtensions of Dir ac's T heor ems

Mo s s in e S . K o u la kz ia n 1, Ca r le n M. Mo s e s ya n 2 a n d Zh o r a G. N iko g h o s ya n 1

1Institute for Informatics and Automation Problems of NAS RA
e-mails: mossine@hotmail.com; zhora@ipia.sci.am
2Faculty of Mathematics, Physics and Informatics

Kh. Abovyan Armenian State University

e-mail: mosesyan@list.ru

Abstract

Let G be a graph on n vertices with degree sequence ± = d1 · d2 · ::: · dn
and let c be the circumference - the length of a longest cycle in G. In 1952, Dirac
proved: (i) every graph with d1 ¸ n2 is hamiltonian; (ii) in every 2-connected graph,
c ¸ minfn; 2d1g. In this paper we present the following two Dirac-type extensions:
(iii) every graph with d± ¸ n2 is hamiltonian; (iv) in every 2-connected graph, c ¸
minfn; 2d±g. The results are sharp.

Keywords: Hamilton cycle, Longest cycle, Circumference, Minimum degree, Degree
sequence.

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

W e c o n s id e r o n ly ¯ n it e u n d ir e c t e d g r a p h s wit h n e it h e r lo o p s n o r m u lt ip le e d g e s . 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 [2 ].

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 ) . L e t n b e
t h e o r d e r ( t h e n u m b e r o f ve r t ic e s ) o f G, c t h e o r d e r o f a lo n g e s t c yc le ( c a lle d c ir c u m fe r e n c e )
in G 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 . W e u s e N ( v ) t o d e n o t e t h e s e t o f a ll n e ig h b o r s o f a
ve r t e x v a n d d( v ) = jN ( v ) j t o d e n o t e t h e d e g r e e o f ve r t e x v. Th e m in im u m d e g r e e in G is
d e n o t e d b y ±. L e t d1; d2; :::; dn b e t h e d e g r e e s e qu e n c e in G wit h ± = d1 · d2 · ::: · dn.

A p a t h ( s im p le p a t h ) o f o r d e r m is a s e qu e n c e o f d is t in c t ve r t ic e s v1; :::; vm, d e n o t e d b y
v1v2:::vm, s u c h t h a t vi¡1vi is a n e d g e fo r a ll 2 · i · m. S im ila r ly. a c yc le o f o r d e r m is a
s e qu e n c e o f d is t in c t ve r t ic e s v1; :::; vm, d e n o t e d b y v1v2:::vmv1, s u c h t h a t vi¡1vi a n d vmv1 a r e
e d g e s fo r a ll 2 · i · m. In p a r t ic u la r , fo r m = 2 , v1v2v1 is a c yc le o f o r d e r 2 ; a n d fo r m = 1 ,
v1v1 is a c yc le o f o r d e r 1 . S o , b y t h e d e ¯ n it io n , e ve r y ve r t e x ( e d g e ) c a n b e c o n s id e r e d a s a
c yc le o f o r d e r 1 ( 2 , r e s p e c t ive ly) . 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 s p a n n in g c yc le .

W e wr it e a c yc le ( a p a t h ) Q wit h a g ive n o r ie n t a t io n b y
¡!
Q . Th e r e ve r s e s e qu e n c e o f

ve r t ic e s o f
¡!
Q is d e n o t e d b y

á
Q . Fo r x 2 V ( Q) , we d e n o t e t h e s u c c e s s o r a n d t h e p r e d e c e s s o r

o f x o n
¡!
Q ( if s u c h ve r t ic e s e xis t ) b y x+ a n d x¡, r e s p e c t ive ly. Fo r U µ V ( Q ) , we d e n o t e

U + = fu+ju 2 Ug a n d U¡ = fu¡ju 2 Ug. W e u s e P = x¡!P y t o d e n o t e a p a t h wit h e n d

1 4



M. Koulakzian, C. Mosesyan and Zh. Nikoghosyan 1 5

ve r t ic e s x a n d y in t h e d ir e c t io n fr o m x t o y. 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 a

p a t h
¡!
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.

In 1 9 5 2 , D ir a c [3 ] g a ve t h e ¯ r s t s u ± c ie n t c o n d it io n fo r a g r a p h t o b e h a m ilt o n ia n a n d
t h e ¯ r s t n o n t r ivia l lo we r b o u n d fo r t h e c ir c u m fe r e n c e in t e r m s o f m in im u m d e g r e e d1 = ±.
T heor em A: [3 ]. E very graph with d1 ¸ n2 is hamiltonian.
T heor em B : [3 ]. In every 2-connected graph, c ¸ m in fn; 2 d1g.
A g r e a t n u m b e r o f g e n e r a liz a t io n s a n d im p r o ve m e n t s o f Th e o r e m s A a n d B a r e kn o wn u n d e r
va r io u s c o n d it io n s .

In t h is p a p e r we p r e s e n t t h e fo llo win g t wo D ir a c -t yp e e xt e n s io n s o f Th e o r e m s A a n d B
in t e r m s o f di ( fo r a p p r o p r ia t e i ) in s t e a d o f d1.
T heor em 1: E very graph with d± ¸ n2 is hamiltonian.
T heor em 2: In every 2-connected graph, c ¸ m in fn; 2 d±g.

It is n o t h a r d t o s e e t h a t if G is a g r a p h wit h d± ¸ n2 o r G is a 2 -c o n n e c t e d g r a p h , t h e n
± ¸ 2 .

To s e e t h a t Th e o r e m 1 a n d Th e o r e m 2 a r e s h a r p , le t G = K± + K±+1. S in c e d± = ±
a n d c = 2 ± < n, we c o n c lu d e t h a t t h e b o u n d d± ¸ n2 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
d± ¸ n¡12 .

L e t G = K± + ( ±K1 [ K2 ) . Cle a r ly, d± = ± a n d d±+1 = ± + 1 . Ob s e r vin g a ls o t h a t
c = 2 ± + 1 < n, we c o n c lu d e t h a t t h e b o u n d d± ¸ n2 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
d±+1 ¸ n2 .

A s fo r Th e o r e m 2 , t h e g r a p h e xa m p le G = K± + K±+1 s h o ws t h a t t h e b o u n d c ¸
m in fn; 2 d±g in Th e o r e m 2 c a n n o t b e r e p la c e d b y c ¸ m in fn; 2 d± + 1 g. Fin a lly, t h e g r a p h
e xa m p le G = K± + ( ±K1 [ K2 ) s h o ws t h a t t h e b o u n d c ¸ m in fn; 2 d±g c a n n o t b e r e p la c e d b y
c ¸ m in fn; 2 d±+1g. Th u s , Th e o r e m 1 a n d Th e o r e m 2 a r e s h a r p in a ll r e s p e c t s .

L e t
¡!
P = v1v2:::vp b e a lo n g e s t p a t h in G. Cle a r ly, N ( v1 ) [ N ( vp ) µ V ( P ) . A vin e o f

le n g t h m o n P is a s e t

fLi = wi
¡!
L izi : 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 ) = fwi; zig ( i = 1 ; :::; m) ,
( b ) v1 = w1 Á w2 Á z1 ¹ w3 Á z2 ¹ w4 Á ::: ¹ wm Á zm¡1 Á zm = vp o n P .

Lemma 1: [3 ]. If G is 2 -connected, then there is at least one vine on P .

W e n e e d a ls o t h e fo llo win g le m m a .
Lemma 2: [1 ]. L et G be a 2-connected graph on n vertices. If v1v2:::vp is a longest path of
G, then there exists a cycle of length at least m in fd( v1 ) + d( vp ) ; ng.

2 . P r o o fs

P r oof of T heor em 1. A s s u m e ¯ r s t t h a t G is n o t c o n n e c t e d a n d le t H1 a n d H2 b e t wo
c o n n e c t e d c o m p o n e n t s o f G. Cle a r ly, jV ( Hi ) j ¸ ± + 1 ( i = 1 ; 2 ) a n d

m a xfd ( v ) : v 2 V ( Hi ) g ¸ d±+1 ( i = 1 ; 2 ) :

H e n c e
2 d± · 2 d±+1 · m a xfd( v ) : v 2 V ( H1 ) g + m a xfd( v ) : v 2 V ( H2 ) g



1 6 New Extensions of Dirac's Theorems

· jV ( H1 ) j + jV ( H2 ) j ¡ 2 · n ¡ 2 ;
c o n t r a d ic t in g t h e h yp o t h e s is 2 d± ¸ n. S o , we c a n a s s u m e t h a t G is c o n n e c t e d . L e t¡!
P = v1v2:::vp b e a lo n g e s t p a t h in G. Cle a r ly, N ( v1 ) [ N ( vp ) µ V ( P ) . A s s u m e t h a t

( a 1 ) P is c h o s e n s o t h a t d ( v1 ) is m a xim u m .

L e t x1; x2; :::; xt b e t h e e le m e n t s o f N ( v1 ) o c c u r r in g o n
¡!
P in a c o n s e c u t ive o r d e r , wh e r e

t = d( v1 ) ¸ ±. Ob s e r ve t h a t fo r e a c h i 2 f2 ; :::; tg,

x¡i
á
P v1xi

¡!
P vp

is a lo n g e s t p a t h in G. B y ( a 1 ) ,

d( v1 ) ¸ d( x¡i ) ( i = 1 ; 2 ; ::; t) : ( 1 )

A s s u m e ¯ r s t t h a t xt = vp, t h a t is c ¸ p. If c ¸ p + 1 , t h e n t h e c yc le o f o r d e r a t le a s t p + 1
c o n t a in s a p a t h o f o r d e r a t le a s t p + 1 , a c o n t r a d ic t io n . H e n c e , c = p. P u t

¡!
C = v1v2:::vpv1.

If p = n, t h e n C is a H a m ilt o n c yc le in G. Ot h e r wis e , s in c e G is c o n n e c t e d , u1u2 2 E ( G ) fo r
s o m e u1 2 V ( C ) a n d u2 62 V ( C ) . Th e n u+1

¡!
C u1u2 is a p a t h o f o r d e r p + 1 , a c o n t r a d ic t io n .

N o w a s s u m e t h a t xt 6= vp, t h a t is xt Á vp. Fu r t h e r , we c a n a s s u m e t h a t

( a 2 ) P is c h o s e n s o t h a t d ( vp ) is m a xim u m , s u b je c t t o ( a 1 ) .

L e t y1; y2; :::; yf b e t h e e le m e n t s o f N ( vp ) o c c u r r in g o n
á
P in a c o n s e c u t ive o r d e r . B y

( a 2 ) ,
d( vp ) ¸ d( y+i ) ( i = 1 ; 2 ; ::; f ) : ( 2 )

B y ( 1 ) a n d ( 2 ) ,
d( v1 ) ¸ m a xfd ( x¡1 ) ; d( x¡2 ) ; :::; d( x¡t ) g

¸ m a xfd1; d2; :::; dtg = dt = dd(v1) ¸ d±:
a n d

d ( vp ) ¸ m a xfd( y+1 ) ; d ( y+2 ) ; :::; d( y+f g
¸ m a xfd1; d2; :::; dfg = df = dd(vp) ¸ d±;

im p lyin g t h a t
d( v1 ) + d ( vp ) ¸ 2 d± ¸ n: ( 3 )

B y L e m m a 2 , G is h a m ilt o n ia n . H o we ve r , we p r e s e n t a s h o r t p r o o f o f t h is fa c t a c c o r d in g
t o t h e la t e s t t e r m in o lo g y.
Case 1. N ( v1 ) \ N + ( vp ) 6= ;.

L e t v 2 N ( v1 ) \ N + ( vp ) , t h a t is v1v; vpv¡ 2 E ( G) . S in c e

v1v
¡!
P vpv

¡Ã¡P v1

is a c yc le o f o r d e r p, we h a ve c ¸ p, im p lyin g t h a t c = p. S in c e G is c o n n e c t e d , we h a ve
c = p = n, t h a t is G is h a m ilt o n ia n .
Case 2. N ( v1 ) \ N + ( vp ) = ;.



M. Koulakzian, C. Mosesyan and Zh. Nikoghosyan 1 7

It fo llo ws t h a t
n ¸ p ¸ jN ( v1 ) j + jN + ( vp ) j + jfv1gj ¸

¸ jN ( v1 ) j + jN ( vp ) j + 1 ¸ d( v1 ) + d ( vp ) + 1 :
B y ( 3 ) , n ¸ 2 d± + 1 , c o n t r a d ic t in g t h e h yp o t h e s is d± ¸ n2 .
P r oof of T heor em 2. L e t

¡!
P = v1v2:::vp b e a lo n g e s t p a t h in G. D e ¯ n e t h e ve r t ic e s

x1; x2; :::; xt; y1; y2; :::; yf a s in p r o o f o f Th e o r e m 1 , wh e r e we h a ve p r o ve d

d ( v1 ) + d( vp ) ¸ 2 d±: ( 4 )

Case 1. xt ¹ yf .
L e t

fLi = wi
¡!
L izi : 1 · i · mg

b e a vin e o f m in im a l le n g t h m o n
¡!
P . S in c e P is a lo n g e s t p a t h in G, we h a ve L1; LM 2 E ( G) .

N e xt , s in c e m is m in im a l, we h a ve xt Á z2, xt Á w3 a n d wm¡1 Á yf , zm¡2 Á yf . Ch o o s e
z¤1 2 V ( P ) s u c h t h a t w2 Á z¤1 a n d jV ( w2

¡!
P z¤1 ) j is m in im a l. A n a lo g o u s ly, c h o o s e w¤m 2 V ( P )

s u c h t h a t w¤m Á zm¡1 a n d jV ( w¤m
¡!
P zm¡1 ) j is m in im a l. P u t

H = P [
m¡1[

i=2

Li [ fv1z¤1 ; vpw¤mg:

B y d e le t in g t h e fo llo win g p a t h s

wi
¡!
P zi¡1 ( i = 3 ; 4 ; :::; m ¡ 1 ) ; w2

¡!
P z¤1; w

¤
m

¡!
P zm¡1

fr o m H ( e xc e p t fo r t h e ir e n d ve r t ic e s ) , we o b t a in a c yc le C wit h a t le a s t d( v1 ) + d( vp ) + 1
ve r t ic e s . B y ( 4 ) ,

c ¸ jV ( C ) j ¸ d ( v1 ) + d( vp ) + 1 > 2 d±:
Case 2. yf Á xt.
Case 2.1. N ( v1 ) \ N + ( vp ) 6= ;.

L e t v 2 N ( v1 ) \ N + ( vp ) , t h a t is v1v; vpv¡ 2 E ( G ) . S in c e

v1v
¡!
P vpv

¡Ã¡P v1

is a c yc le o f o r d e r p a n d G is c o n n e c t e d , e it h e r p < jV ( G ) j a n d we c a n fo r m a p a t h lo n g e r
t h a n P ( a c o n t r a d ic t io n ) o r p = jV ( G ) j, im p lyin g t h a t c = p = n.
Case 2.2. N ( v1 ) \ N + ( vp ) = ;.

S in c e yf Á xt, we c a n c h o o s e xi 2 N ( v1 ) a n d yj 2 N ( vp ) s u c h t h a t yj Á xi a n d
v1v; vpv 62 E ( G ) fo r e a c h ve r t e x v wit h yj Á v Á xi. P u t

C = v1xi
¡!
P vpyi

á
P v1:

Th e n
c ¸ jV ( C ) j ¸ jN ( v1 ) j + jN + ( vp ) j + jfv1gj ¡ jfyjgj

¸ jN ( v1 ) j + jN ( vp ) j = d ( v1 ) + d( vp ) :
B y ( 4 ) , c ¸ 2 d±.



1 8 New Extensions of Dirac's Theorems

3 . A c kn o wle d g m e n t s

W e wo u ld like t o t h a n k t h e r e fe r e e s fo r u s e fu l s u g g e s t io n s , wh ic h h a ve c o n s id e r a b ly im p r o ve d
t h e p r e s e n t a t io n o f t h e p a p e r .

Refer ences

[1 ] 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 yc le s " , H a n d b o o k o f Co m b in a t o r ic s ,
vo l.1 , E ls e vie r , A m s t e r d a m , p p . 5 -1 1 0 , 1 9 9 5 .

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

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

Submitted 22.08.2017, accepted 04.12.2017.

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

Ø. øáõɳù½Û³Ý, Î. Øáë»ëÛ³Ý ¨ Ä. ÜÇÏáÕáëÛ³Ý

²Ù÷á÷áõÙ

¸Çóáõù G-Ý ± Ýí³½³·áõÛÝ ³ëïÇ×³Ý ¨ ± = d1 · d2 · ::: · dn ³ëïÇ׳ݳÛÇÝ
ѳçáñ¹³Ï³ÝáõÃÛáõÝ áõÝ»óáÕ n ·³·³Ã³ÝÇ ·ñ³ý ¿: G-Ç ³Ù»Ý³»ñϳñ óÇÏÉÇ
»ñϳñáõÃÛáõÝÁ Ý߳ݳÏíáõÙ ¿ c-áí: 1952-ÇÝ ¸Çñ³ÏÝ ³å³óáõó»ó, áñ (i) d1 ¸ n2 å³ÛÙ³ÝÇÝ
µ³í³ñ³ñáÕ Ï³Ù³Û³Ï³Ý ·ñ³ý áõÝÇ Ð³ÙÇÉïáÝÇ óÇÏÉ. (ii) Ï³Ù³Û³Ï³Ý 2-ϳå³Ïóí³Í
·ñ³ýáõÙ c ¸ m in fn; 2 d1g: Ü»ñϳ ³ß˳ï³ÝùáõÙ µ»ñíáõÙ »Ý Ýßí³Í ³ñ¹ÛáõÝùÝ»ñÇ »ñÏáõ
ÁݹɳÛÝáõÙÝ»ñ.(iii) d± ¸ n2 å³ÛÙ³ÝÇÝ µ³í³ñ³ñáÕ Ï³Ù³Û³Ï³Ý ·ñ³ý áõÝÇ Ð³ÙÇÉïáÝÇ
óÇÏÉ, (iv) Ï³Ù³Û³Ï³Ý 2-ϳå³Ïóí³Í ·ñ³ýáõÙ c ¸ m in fn; 2 d±g: êï³óí³Í ³ñ¹ÛáõÝùÝ»ñÁ
»Ýóϳ ã»Ý µ³ñ»É³íÙ³Ý:

Íîâûå îáîáùåíèÿ òåîðåì Äèðàêà
Ì. Êóëàêçÿí, Ê. Ìîñåñÿí è Æ. Íèêîãîñÿí

Àííîòàöèÿ

Ïóñòü ± = d1 · d2 · ::: · dn ïîñëåäîâàòåëüíîñòü ñòåïåíåé âåðøèí n-
âåðøèííîãî ãðàôà G ñ ìèíèìàëüíîé ñòåïåíüþ ±. Äëèíà äëèííåéøåãî öèêëà
ãðàôà îáîçíà÷àåòñÿ ÷åðåç c.  1952 ãîäó Äèðàê äîêàçàë, ÷òî (i) êàæäûé ãðàô
óäîâëåòâîðÿþùèé óñëîâèþ d1 ¸ n2 , èìååò Ãàìëüòîíîâ öèêë; (ii) åñëè G ÿâëÿåòñÿ
2-ñâÿçíûì ãðàôîì, òî c ¸ m in fn; 2 d1g. Â íàñòîÿùåé ðàáîòå äîêàçûâàþòñÿ: (iii)
êàæäûé ãðàô óäîâëåòâîðÿþùèé óñëîâèþ d± ¸ n2 , èìååò Ãàìëüòîíîâ öèêë; (iv)
åñëè G ÿâëÿåòñÿ 2-ñâÿçíûì ãðàôîì, òî c ¸ m in fn; 2 d±g. Ïîëó÷åííûå ðåçóëüòàòû
íåóëó÷øàåìû.