3_Mossine_19--22.DVI


Mathematical Problems of Computer Science 48, 19{22, 2017.

On Long Cycles in Gr aphs in T er ms of Degr ee

Sequences

Mo s s in e S . K o u la kz ia n

Institute for Informatics and Automation Problems of NAS RA

e-mail: mossine@hotmail.com

Abstract

Let G be a graph on n vertices with degree sequence ± = d1 · d2 · ::: · dn. Let
m be the number of connected components of G, c the circumference - the order of
a longest cycle, p the order of a longest path in G and ¾s the minimum degree sum
of an independent set of s vertices. In this paper it is shown that in every graph G,
c ¸ d¾m+m + 1. This bound is best possible and generalizes the earliest lower bound
for the circumference due to Dirac (1952): c ¸ ± + 1 = d1 + 1. As corollaries, we have:
(i) c ¸ d±+1 + 1; (ii) if d¾m+m ¸ p ¡ 1, then c = p; (iii) if G is a connected graph with
d±+1 ¸ p ¡ 1, then G is hamiltonian; (iv) if d¾m+m ¸ n ¡ 1, then G is hamiltonian.

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

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 . 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 ± a n d t h e m in im u m d e g r e e s u m o f a n in d e p e n d e n t s e t o f s ve r t ic e s will b e d e n o t e d b y ¾s.
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. 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 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.

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 p r e d e c e s s o r o f x o n ¡!Q ( if s u c h

1 9



2 0 On Long Cycles in Graphs in Terms of Degree Sequences

ve r t ic e s e xis t ) b y x¡. 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 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.
Th e e a r lie s t a n d s im p le s t lo we r b o u n d fo r t h e c ir c u m fe r e n c e wa s o b t a in 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 ±.
T heor em A: [2 ]. In every graph, c ¸ ± + 1 .

Th e o r e m A is b e s t p o s s ib le . H o we ve r , t h e b o u n d c ¸ ± + 1 in Th e o r e m A is e qu iva le n t t o
c ¸ d1 + 1 , wh ic h is fa r fr o m b e in g b e s t p o s s ib le . In t h is p a p e r we p r e s e n t a n im p r o ve m e n t
o f Th e o r e m A in t e r m s o f d e g r e e s e qu e n c e s wit h o u t a n y a d d it io n a l c o n d it io n s .
T heor em 1: L et G be a graph with m connected components and degree sequence ± = d1 ·
d2 · ::: · dn. Then c ¸ d¾m+m + 1 .

If G = mK±+1, t h e n c = ± + 1 = dm±+m + 1 = d¾m+m + 1 . Th is g r a p h e xa m p le s h o ws
t h a t t h e b o u n d d¾m+m + 1 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¾m+m + 2 . N e xt , le t
G = m ( K± + K±+1 ) . Th e n d¾m+m+1 = dm±+m+1 = 2 ± = c. Th is g r a p h e xa m p le s h o ws t h a t
t h e lo we r b o u n d d¾m+m +1 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¾m+m+1 +1 . Th u s , Th e o r e m
1 is b e s t p o s s ib le in a ll r e s p e c t s .
Cor ollar y 1: L et G be a graph with degree sequence ± = d1 · d2 · ::: · dn. Then
c ¸ d±+1 + 1 .

Th e g r a p h K± + ( ± + 1 ) K1 is ±-c o n n e c t e d wit h d1 = d2 = ::: = d±+1 = ± a n d d±+2 = 2 ±.
S in c e c = 2 ± a n d d±+2 + 1 = 2 ± + 1 , t h e b o u n d c ¸ d±+1 + 1 in Co r o lla r y 1 c a n n o t b e r e p la c e d
b y c ¸ d±+2 + 1 . Th u s , Co r o lla r y 1 is b e s t p o s s ib le e ve n fo r h ig h c o n n e c t e d g r a p h s .

Th e n e xt t h r e e s t a t e m e n t s c a n b e o b t a in e d fr o m Th e o r e m 1 e a s ily.
T heor em 2: L et G be a graph with m connected components and degree sequence ± = d1 ·
d2 · ::: · dn. If d¾m+m ¸ p ¡ 1 , then c = p.
Cor ollar y 2: L et G be a graph with degree sequence ± = d1 · d2 · ::: · dn. If d±+1 ¸ p ¡ 1 ,
then c = p.
T heor em 3: L et G be a graph with degree sequence ± = d1 · d2 · ::: · dn. If d±+1 ¸ p ¡ 1 ,
then G is hamiltonian.
T heor em 4: L et G be a graph with degree sequence ± = d1 · d2 · ::: · dn. If d±+1 ¸ n ¡ 1 ,
then G is hamiltonian.

2 . P r o o fs

P r oof of T heor em 1. L e t H1; H2; :::; Hm 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 G a n d le t¡!
P = u

¡!
P v b e a lo n g e s t p a t h in H1. Cle a r ly, N ( u ) µ V ( P ) . A s s u m e t h a t

( a ) P is c h o s e n in H1 s o t h a t d( u ) 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 ( u ) 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( u ) ¸ ±. Ob s e r ve t h a t fo r e a c h i 2 f 1 ; 2 ; :::; tg,

x¡i
á
P uxi

¡!
P v

is a lo n g e s t p a t h in H1, im p lyin g t h a t

N ( x¡i ) µ V ( P ) ( i = 1 ; 2 ; :::; t ) :

B y ( a ) ,
d ( u ) ¸ d( x¡i ) ( i = 1 ; 2 ; ::; t) ; d( u ) ¸ d ( v ) : ( 1 )



M. Koulakzian 2 1

P u t C = u
¡!
P xtu. Cle a r ly,

c ¸ jV ( C ) j ¸ t + 1 = d ( u) + 1 :

B y ( 1 ) ,

d( u ) ¸ maxfd ( x¡1 ) ; d( x¡2 ) ; :::; d( x¡t ) ; d( v ) g;

im p lyin g t h a t

c ¸ d( u ) + 1 ¸ maxfd( x¡1 ) ; d( x¡2 ) ; :::; d( x¡d(u) ) ; d( v ) g + 1 :

A n a lo g o u s ly, fo r e a c h i 2 f 1 ; 2 ; :::; mg, we c a n ¯ n d p a ir wis e d is t in c t ve r t ic e s yi1; yi2; :::; yid(ui)+1
in Hi s u c h t h a t

c ¸ m a xfd( yi1 ) ; d( yi2 ) ; :::; d( yid(ui)+1 ) g + 1 ;

wh e r e ui 2 V ( Hi ) . S in c e t h e ve r t ic e s

y11; y
1
2 ; :::; y

1
d(u1)+1

;

y21; y
2
2 ; :::; y

2
d(u2)+1

;

::::::::::::::::::::::::::

ym1 ; y
m
2 ; :::; y

m
d(um)+1

a r e a ll p a ir wis e d is t in c t , fo r s o m e p a ir wis e d is t in c t ve r t ic e s z1; z2; :::; zd(u1)+d(u2)+:::+d(um)+m
we h a ve

c ¸ m a xfd ( z1 ) ; d( z2 ) ; :::; d( zd(u1)+d(u2)+:::+d(um)+m ) g + 1

¸ m a xfd1; d2; :::; dd(u1)+d(u2)+:::+d(um)+mg + 1

= dd(u1)+d(u2)+:::+d(um)+m + 1 :

Ob s e r vin g a ls o t h a t fu1; u2; :::; umg is a n in d e p e n d e n t s e t o f ve r t ic e s , we o b t a in t h e d e s ir e d
b o u n d c ¸ d¾m+m + 1 .

P r oof of T heor em 2. B y Th e o r e m 1 , c ¸ d¾m+m + 1 ¸ p. If c ¸ p + 1 , t h e n c le a r ly 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 wit h a t le a s t p + 1 ve r t ic e s , c o n t r a d ic t in g t h e
fa c t t h a t t h e lo n g e s t p a t h in G h a s e xa c t ly p ve r t ic e s . H e n c e , c = p.

P r oof of T heor em 3. L e t G b e a c o n n e c t e d g r a p h wit h d±+1 ¸ p ¡ 1 . S in c e m = 1 a n d
d¾m+m ¸ p ¡ 1 , b y Th e o r e m 2 , c = p. L e t

¡!
C b e a lo n g e s t c yc le in G o f le n g t h p. If p = n,

t h e n G is h a m ilt o n ia n . L e t p < n. S in c e G is c o n n e c t e d , we h a ve vu 2 E ( G ) fo r s o m e
v 2 V ( C ) a n d u 2 G ¡ C. Th e n

uv
¡!
C v¡

is a p a t h o n p + 1 ve r t ic e s , a c o n t r a d ic t io n .

Th e o r e m 4 fo llo ws fr o m Th e o r e m 2 im m e d ia t e ly.



2 2 On Long Cycles in Graphs in Terms of Degree Sequences

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 .

Submitted 22.08.2017, accepted 06.12.2017.

¶ñ³ýÝ»ñáõÙ »ñϳñ óÇÏÉ»ñÇ Ù³ëÇÝ ³ëïÇ׳ݳÛÇÝ
ѳçáñ¹³Ï³ÝáõÃÛáõÝÝ»ñÇ É»½íáí

Ø. øáõɳù½Û³Ý

²Ù÷á÷áõÙ

¸Çóáõù G-Ý ± Ýí³½³·áõÛÝ ³ëïÇ×³Ý ¨ ± = d1 · d2 · ::: · dn ³ëïÇ׳ݳÛÇÝ 
ѳçáñ¹³Ï³ÝáõÃÛáõÝ áõÝ»óáÕ n ·³·³Ã³ÝÇ ·ñ³ý ¿: ¶ñ³ýÇ Ï³å³Ïóí³ÍáõÃÛ³Ý 
µ³Õ³¹ñÇãÝ»ñÇ ù³Ý³ÏÁ ÏÝ߳ݳϻÝù m-áí, ³Ù»Ý³»ñϳñ óÇÏÉÇ »ñϳñáõÃÛáõÝÁ` c-

áí, ÇëÏ s ³ÝÏ³Ë ·³·³ÃÝ»ñÇ ³ëïÇ׳ÝÝ»ñÇ Ýí³½³·áõÛÝ ·áõÙ³ñÁ` ¾s -áí: Ü»ñϳ
³ß˳ï³ÝùáõÙ ³å³óáõóíáõÙ ¿, áñ Ï³Ù³Û³Ï³Ý ·ñ³ýáõÙ c ¸ d¾m+m + 1 : êï³óí³Í
·Ý³Ñ³ï³Ï³ÝÁ »Ýóϳ ã¿ µ³ñ»É³íÙ³Ý ¨ ÁݹѳÝñ³óÝáõÙ ¿ 1952-ÇÝ ¸Çñ³ÏÇ ÏáÕÙÇó
ëï³óí³Í c ¸ ± + 1 = d1 + 1 ·Ý³Ñ³ï³Ï³ÝÁ:

Î äëèííåéøèõ öèêëàõ ãðàôà â òåðìèíàõ
ïîñëåäîâàòåëüíîñòè ñòåïåíåé âåðøèí

Ì. Êóëàêçÿí

Àííîòàöèÿ

Ïóñòü ±=d1·d2·::: ·dn - ïîñëåäîâàòåëüíîñòü ñòåïåíåé âåðøèí n-âåðøèííîãî
ãðàôà G ñ ìèíèìàëüíîé ñòåïåíüþ ±. ×èñëî êîìïîíåíò ñâÿçíîñòè ãðàôà G
îáîçíà÷àåòñÿ ÷åðåç m, äëèíà äëèííåéøåãî öèêëà - ÷åðåç c, à ìèíèìàëüíîå
÷èñëî ñóìì ñòåïåíåé s íåçàâèñèìûõ âåðøèí -÷åðåç ¾s.  íàñòîÿùåé ðàáîòå
äîêàçûâàåòñÿ, ÷òî â ëþáîì ãðàôå G, c ¸ d¾m+m + 1 . Ïîëó÷åííàÿ îöåíêà
íåóëó÷øàåìà è îáîáùàåò îöåíêó c ¸ ± + 1 = d1 + 1 Äèðàêà (1952).