4_Mossine-dominant_35-40.DVI


Mathematical Problems of Computer Science 49, 35{40, 2018.

Degr ee Sequences and Dominating Cycles in

2-Connected Gr aphs

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

Institute for Informatics and Automation Problems of NAS RA

e-mail: zhora@ipia.sci.am

Abstract

Let G be a graph on n vertices and minimum degree ± with degree sequence ± =
d1 · d2 · ::: · dn. The minimum degree sum of two nonadjacent vertices in G is
denoted by ¾2. Let c be the circumference - the order (the number of vertices) of a
longest cycle, and p be the order of a longest path in G. In 1952, Dirac proved: (1)
if G is a 2-connected graph, then c ¸ minfn; 2d1g; (2) every graph with d1 ¸ n2 is
hamiltonian. Recently, these results were improved by Nikoghosyan in terms of degree
sequences: (3) if G is a 2-connected graph, then c ¸ minfn; d± + d±+1g; (4) every graph
with d± + d±+1 ¸ n is hamiltonian. In this paper we present the dominating cycle
versions of these theorems: (i) if G is a 2-connected graph, then either c ¸ d± + d¾2
or c ¸ p ¡ 1 (that is G has a dominating cycle); (ii) every 2-connected graph with
d± + d±+1 ¸ p ¡ 1 has a dominating cycle. The results are sharp.

Keywords: Hamilton cycle, dominating cycle, circumference, minimum degree,
degree sums, 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 s u m o f t wo
n o n a d ja c e n t ve r t ic e s in G is d e n o t e d b y ¾2. In p a r t ic u la r , t h 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.
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. 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 . A c yc le C o f G is c a lle d a d o m in a t in g c yc le if e ve r y e d g e o f G h a s a t
le a s t o n e o f it s e n d ve r t ic e s o n C, o r , e qu iva le n t ly, if G ¡ V ( C ) c o n t a in s n o e d g e s .

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

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 s a y t h a t t h e ve r t e x

3 5



3 6 Degree Sequences and Dominating Cycles in 2-Connected Graphs

z1 p r e c e d e s t h e 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. 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 = 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 .

Th e fo llo win g r e s u lt g u a r a n t e e s t h e e xis t e n c e o f a t le a s t o n e vin e o n
¡!
P in a 2 -c o n n e c t e d

g r a p h .

T he Vine Lemma [2 ]. If G is a 2 -c o n n e c t e d g r a p h a n d P a p a t h in G, t h e n t h e r e is a t
le a s t o n e vin e o n P .

In 1 9 5 2 , D ir a c [2 ] o b t a in e d t h e ¯ r 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 fo r 2 -c o n n e c t e d
g r a p h s a n d t h e ¯ r s t s u ± c ie n t c o n d it io n fo r H a m ilt o n c yc le s in t e r m s o f m in im u m d e g r e e ±.

T heor em A [2 ]. If G is a 2-connected graph, then c ¸ m in fn; 2 ±g = m in fn; 2 d1g.

T heor em B [2 ]. E ve r y g r a p h wit h ± = d1 ¸ n2 is h a m ilt o n ia n .

Th e o r e m s A a n d B we r e im p r o ve d in [3 ] in t e r m s o f d e g r e e s e qu e n c e s .

T heor em C [3 ]. If G is a 2-connected graph, then c ¸ m in fn; d± + d±+1g.

T heor em D [3 ]. E very graph with d± + d±+1 ¸ n is hamiltonian.

In t h is p a p e r we p r e s e n t t h e d o m in a t in g ve r s io n s o f Th e o r e m s C a n d D .

P r oposition 1 [4 ]. L et G be a connected graph with c ¸ p ¡ 1 . Then every longest cycle in
G is a dominating cycle.

T heor em 1. If G is a 2-connected graph, then c ¸ m in fp ¡ 1 ; d± + d¾2g.

Th e n e xt r e s u lt fo llo ws fr o m Th e o r e m 1 im m e d ia t e ly a s a s u ± c ie n t c o n d it io n fo r t h e
e xis t e n c e o f a d o m in a t in g c yc le .

T heor em 2. If G is a 2-connected graph with d± + d¾2 ¸ p ¡ 1 , then c ¸ p ¡ 1 .

If G = K±+1 + K±, t h e n d± = ±, d2± = d¾2 = 2 ± = ¾2 a n d c = 2 ± = ¾2 = p ¡ 1 . Th is
g r a p h e xa m p le s h o ws t h a t t h e c o n c lu s io n " e it h e r c ¸ d± + d¾2 o r c ¸ p ¡ 1 " in Th e o r e m 3
c a n n o t b e r e p la c e d b y " e it h e r c ¸ d± + d¾2 o r c ¸ p " . N e xt , le t G = ±K2 + K±¡1. Th e n
d± = d2± = d¾2 = ±, d2±+1 = d¾2+1 = 3 ± ¡ 2 a n d c = 3 ± ¡ 3 = p ¡ 2 . Th is g r a p h e xa m p le
s h o ws t h a t t h e c o n c lu s io n " e it h e r c ¸ d± + d¾2 o r c ¸ p¡ 1 " in Th e o r e m 1 c a n n o t b e r e p la c e d



M. Koulakzyan 3 7

b y " e it h e r c ¸ d± + d¾2+1 o r c ¸ p ¡ 1 " . Th u s , Th e o r e m 1 is b e s t p o s s ib le .

2 . P r o o fs

P r oof of T heor em 1. 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 .

( 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 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 ) ¸ ±. N e xt , le 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 . If e it h e r xt = vp o r yf = v1, t h e n 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 .
H e n c e , xt 6= vp a n d yf 6= v1. Ob s e r ve t h a t fo r e a c h i 2 f1 ; 2 ; :::; tg,

x¡i
á
P v1xi

¡!
P vp

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

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

B y a s ym m e t r ic a r g u m e n t ,

N ( y+i ) µ V ( P ) ( i = 1 ; 2 ; :::; f ) :
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 . S in c e t h e ve r t ic e s x¡1 ; x

¡
2 ; :::; x

¡
t ; y

+
1 ; y

+
2 ; :::; y

+
f a r e p a ir wis e d is t in c t , we h a ve

d( v1 ) = m a xfd ( x¡1 ) ; d( x¡2 ) ; :::; d( x¡t ) ; d( y+1 ) ; d ( y+2 ) ; :::; d( y+f ) g



3 8 Degree Sequences and Dominating Cycles in 2-Connected Graphs

¸ m a xfd1; d2; :::; dt+fg = dt+f = dd(v1)+d(vp) ¸ d¾2 ;
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
c ¸ d( v1 ) + d( vp ) + 1 > d± + d¾2 :

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.

Case 2.2. N ( v1 ) \ N + ( vp ) = ;.
Case 2.2.1. N¡ ( v1 ) \ N + ( vp ) 6= ;.
L e t v 2 N¡ ( v1 ) \ N + ( vp ) , t h a t is z = x¡i = y+j fo r s o m e i 2 f 1 ; :::; tg a n d j 2 f 1 ; :::; fg.

Cle a r ly,

v1z
+¡!P vpz¡

á
P v1

is a c yc le o f o r d e r p ¡ 1 , t h a t is c ¸ p ¡ 1 .

Case 2.2.2. N¡ ( v1 ) \ N + ( vp ) = ;.
S in c e yf Á xt, we c a n c h o o s e t wo in t e g e r s 1 · a · t a n d 1 · b · f s u c h t h a t yb Á xa,

a n d jV ( yb
¡!
P xp ) j is m in im u m . P u t

C = v1xa
¡!
P vpyb

á
P v1:

Cle a r ly,
( N ( v1 ) [ N + ( vp ) ) ¡ y+b µ V ( C ) :

H e n c e ,
c ¸ jV ( C ) j ¸ j ( N ( v1 ) [ N + ( vp ) ) ¡ y+b j + jfv1gj

= jN ( v1 ) j + jN + ( vp ) j = jN ( v1 ) j + jN ( vp ) j = d( v1 ) + d ( vp ) :
B y t h e h yp o t h e s is , t h e fo llo win g ve r t ic e s

x¡1 ; x
¡
2 ; :::; x

¡
t ; y

+
1 ; y

+
2 ; :::; y

+
f

a r e p a ir wis e d is t in c t . B y ( a 1 ) a n d ( a 2 ) ,

d ( v1 ) = m a xfd ( x¡1 ) ; d( x¡2 ) ; :::; d( x¡t ) ; d( y+1 ) ; d( y+2 ) ; :::; d( y+f ) g

¸ m a xfd1; d2; :::; dt+fg = dt+f = dd(v1)+d(vp) ¸ d¾2 ;
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

c ¸ d ( v1 ) + d( vp ) ¸ d± + d¾2:



M. Koulakzyan 3 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 ] Zh . G. N iko g h o s ya n , \ D e g r e e s e qu e n c e s a n d lo n g c yc le s in Gr a p h s " , A r X iv:1 7 1 1 .0 4 1 3 4
( 2 0 1 7 ) 9 p a g e s .

[4 ] 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 Combin., vo l. 2 8 , p p . 8 5 9 -8 6 8 , 2 0 1 2 .

Submitted 22.08.2017, accepted 14.12.2017.

²ëïÇ׳ݳÛÇÝ Ñ³çáñ¹³Ï³ÝáõÃÛáõÝÝ»ñ ¨ ¹áÙÇݳÝï óÇÏÉ»ñ
2-ϳå³Ïóí³Í ·ñ³ýÝ»ñáõÙ

Ø. øáõɳù½Û³Ý

²Ù÷á÷áõÙ

¸Çóáõù G-Ý n ·³·³Ã³ÝÇ ·ñ³ý ¿ ± Ýí³½³·áõÛÝ ³ëïÇ׳Ýáí ¨ ± = d1 · d2 · · dn
³ëïÇ׳ݳÛÇÝ Ñ³çáñ¹³Ï³ÝáõÃÛ³Ùµ: ²Ù»Ý³»ñϳñ óÇÏÉÇ »ñϳñáõÃÛáõÝÁ Ý߳ݳÏíáõÙ
¿ c-áí, ÇëÏ ³Ù»Ý³»ñϳñ ßÕóÛÇ »ñϳñáõÃÛáõÝÁ (·³·³ÃÝ»ñÇ ù³Ý³ÏÁ) p-áí: 1952-ÇÝ
¸Çñ³ÏÝ ³å³óáõó»ó. (1) »Ã» G-Ý 2-ϳå³Ïóí³Í ·ñ³ý ¿, ³å³ c ¸ m in fn; 2 d1g, (2)
Ï³Ù³Û³Ï³Ý ·ñ³ý, áñÁ µ³í³ñ³ñáõÙ ¿ d1 ¸ n2 å³ÛÙ³ÝÇÝ, ѳÙÇÉïáÝÛ³Ý ¿: ì»ñç»ñë
³Ûë ³ñ¹ÛáõÝùÝ»ñÁ ɳí³óí»óÇÝ ³ëïÇ׳ݳÛÇÝ Ñ³çáñ¹³Ï³ÝáõÃÛáõÝÝ»ñÇ É»½íáí` (3)
Ï³Ù³Û³Ï³Ý 2-ϳå³Ïóí³Í ·ñ³ýáõÙ c ¸ m in fn; d± + d±+1g, (4) d± + d±+1 ¸ n å³ÛÙ³ÝÇÝ
µ³í³ñ³ñáÕ Ï³Ù³Û³Ï³Ý ·ñ³ý ѳÙÇÉïáÝÛ³Ý ¿ (Zh.G. Nikoghosyan, Degree Sequences
and Long Cycles in Graphs, ArXiv:1711.04134): Ü»ñϳ ³ß˳ï³ÝùáõÙ µ»ñíáõÙ »Ý (3) ¨
(4) ûáñ»ÙÝ»ñÇ ï³ñµ»ñ³ÏÝ»ñÁ ¹áÙÇݳÝï óÇÏÉ»ñÇ Ñ³Ù³ñ: êï³óí³Í ³ñ¹ÛáõÝùÝ»ñÁ
ɳí³óÝ»ÉÇ ã»Ý:



4 0 Degree Sequences and Dominating Cycles in 2-Connected Graphs

Ñòåïåííûå ïîñëåäîâàòåëüíîñòè è äîìèíàíòíûå öèêëû
â 2-ñâÿçíûõ ãðàôàõ

Ì. Êóëàêçÿí

Àííîòàöèÿ

Ïóñòü G ÿâëÿåòñÿ n âåðøèííûì ãðàôîì ñ ìèíèìàëüíîé ñòåïåíüþ ± è
ñòåïåííîé ïîñëåäîâàòåëüíîñòüþ ± = d1 · d2 · · dn. Äëèíà äëèííåéøåãî
öèêëà îáîçíà÷àåòñÿ ÷åðåç c, à äëèíà äëèííåéøåé öåïè (÷èñëî å¸ âåðøèí) -
÷åðåç p.  1952 ãîäó Äèðàê äîêàçàë: (1) åñëè G ÿâëÿåòñÿ 2-ñâÿçíûì ãðàôîì,
òî c ¸ m in fn; 2 d1g; (2) åñëè ãðàô óäîâëåòâîðÿåò óñëîâèþ d1 ¸ n2 , òî îí ÿâëÿåòñÿ
ãàìèëüòîíîâûì. Íåäàâíî ýòè ðåçóëüòàòû áûëè óëó÷øåíû â òåðìèíàõ ñòåïåííûõ
ïîñëåäîâàòåëüíîñòåé: (3) åñëè G ÿâëÿåòñÿ 2-ñâÿçíûì ãðàôîì, òî c ¸ m in fn; d± +
d±+1g; (4) åñëè ãðàô óäîâëåòâîðÿåò óñëîâèþ d± + d±+1 ¸ n, òî îí ÿâëÿåòñÿ
ãàìèëüòîíîâûì (Zh.G. Nikoghosyan, Degree Sequences and Long Cycles in Graphs,
ArXiv:1711.04134). Â íàñòîÿùåé ðàáîòå ïðåäñòàâëÿþòñÿ âåðñèè òåîðåì (3) è (4)
äëÿ äîìèíàíòíûõ öèêëîâ. Ïîëó÷åííûå ðåçóëüòàòû íåóëó÷øàåìû.