D:\Final_47\...\Nikoghosyan.DVI


Mathematical Problems of Computer Science 47, 30{36, 2017.

On Longest Cycles in 2-connected Gr aphs

Mo s s in e S . K o u la kz ia n a n d Zh o r a G. N iko g h o s ya n

Institute for Informatics and Automation Problems of NAS RA

e-mail: mossine@hotmail.com, zhora@ipia.sci.am

Abstract

For a graph G, n denotes the order (the number of vertices) of G, c the order
of a longest cycle in G (called circumference), p the order of a longest path and ±
the minimum degree. In 1952, Dirac proved: (i) if G is a 2-connected graph, then
c ¸ minfn; 2±g. The bound 2± in (i) was enlarged independently by Bondy (1971),
Bermond (1976) and Linial (1976) in terms of ¾2 - the minimum degree sum of two
nonadjacent vertices: (ii) if G is a 2-connected graph, then c ¸ minfn; ¾2g. In this
paper two further extensions of (i) and (ii) are presented by incorporating p and the
length of a vine on a longest path of G as new parameters along with n, ± and ¾2.

Keywords: Hamilton cycle, Dominating cycle, Longest cycle, Longest path, Mini-
mum degree, Degree sums.

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 . 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 ¾1 is d e n o t e d
b y ±. 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 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 .

Th e e a r lie 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 wa s o b t a in e d in 1 9 5 2 d u e t o
D ir a c [4 ] in t e r m s o f ± a n d n.
T heor em A: [4 ]. In every 2-connected graph, c ¸ m in fn; 2 ±g.

Th e b o u n d 2 ± in Th e o r e m A wa s e n la r g e d in d e p e n d e n t ly b y B o n d y [1 ], B e r m o n d [3 ] a n d
L in ia l [5 ] in t e r m s o f ¾2.
T heor em B : [1 ],[3 ],[5 ]. In every 2-connected graph, c ¸ m in fn; ¾2g.

In t h is p a p e r t wo fu r t h e r e xt e n s io n s o f t h e s e r e s u lt s a r e p r e s e n t e d b y in c o r p o r a t in g p a n d
t h e le n g t h o f a vin e o n a lo n g e s t p a t h o f G in c o r r e s p o n d in g b o u n d s a s n e w p a r a m e t e r s a lo n g
wit h n, ± a n d ¾2. Th e vin e 's d e ¯ n it io n n e e d s s o m e a d d it io n a l n o t a t io n .

If Q is a p a t h o r a c yc le , t h e n t h e le n g t h o f Q, d e n o t e d b y l ( Q) , is jE ( Q ) j - t h e n u m b e r o f
e d g e s in Q. 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

3 0



M. Koulakzian and Zh. Nikoghosyan 3 1

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.

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.

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. 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 f le n g t h m 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 .
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 in a 2 -c o n n e c t e d g r a p h .

Lemma: (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 .

In t h e p a p e r , we o b t a in a 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 n, ¾2 a n d t h e
le n g t h m o f a vin e o n a lo n g e s t p a t h o f G.
T heor em 1: L et G be a 2-connected graph and fL1; L2; :::; Lmg be a vine on a longest path
of G. Then

c ¸ m in fn; ¾2 + m ¡ 2 g:

Th e m in im u m d e g r e e ve r s io n o f Th e o r e m 1 fo llo ws im m e d ia t e ly.
Cor ollar y 1: L et G be a 2-connected graph and fL1; L2; :::; Lmg be a vine on a longest path
of G. Then

c ¸ m in fn; 2 ± + m ¡ 2 g:

If m = 1 in Th e o r e m 1 , t h e n c le a r ly G is h a m ilt o n ia n . Th e r e fo r e , Th e o r e m 1 is a n
e xt e n s io n o f Th e o r e m s A a n d B b y in c o r p o r a t in g p a r a m e t e r m a lo n g wit h n a n d ¾2.

N e xt , we o b t a in a lo we r b o u n d fo r t h e c ir c u m fe r e n c e c in t e r m s o f ¾2 a n d p.
T heor em 2: L et G be 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 + 1
4
( ¾2 ¡ 7 ) 2 + 12 ( ¾2 + 1 ) wh e n p ¸ ¾3 ¡ 1 :

Th e o r e m 2 c a n b e c o n s id e r e d a s a n o t h e r e xt e n s io n o f Th e o r e m s A a n d B . In d e e d , if
p · ¾2, t h e n b y Th e o r e m 2 , c ¸ p, im p lyin g t h a t c = p = n ¸ m in fn; ¾2g. N e xt , if
¾2 + 1 · p · ¾3 ¡ 2 , t h e n b y Th e o r e m 2 , c ¸ p ¡ 1 ¸ ¾2 ¸ m in fn; ¾2g. Fin a lly, if p ¸ ¾3 ¡ 1 ,
t h e n o b s e r vin g t h a t 2 ¾3 ¸ 3 ¾2, we g e t

s
2 p ¡ 1 0 + 1

4
( ¾2 ¡ 7 ) 2 ¸

s
2 ( ¾3 ¡ 1 ) ¡ 1 0 +

1

4
( ¾2 ¡ 7 ) 2 =

1

2
( ¾2 ¡ 1 ) ;

a n d b y Th e o r e m 2 , c ¸ ¾2 ¸ m in fn; ¾2g.



3 2 On Longest Cycles in 2-connected Graphs

Th e m in im u m d e g r e e ve r s io n o f Th e o r e m 2 fo llo ws im m e d ia t e ly.
Cor ollar y 2: L et G be 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 :

Th e s p e c ia l c a s e s c ¸ p a n d c ¸ p ¡ 1 in Th e o r e m 2 c a n b e in t e r p r e t e d in t e r m s o f
H a m ilt o n a n d d o m in a t in g c yc le s b y t h e fo llo win g t wo p r o p o s it io n s .
P r oposition 1: [6 ]. A connected graph is hamiltonian if and only if c = p.
P r oposition 2: [6 ]. L et G be a connected graph with c ¸ p ¡ 1 . Then every longest cycle
in G is a dominating cycle.

To s h o w t h a t t h e b o u n d s in Co r o lla r y 2 ( a s we ll a s in Th e o r e m 2 ) a r e s h a r p , 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 Co r o lla r y
2 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 wit h 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 wit h 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 wit h 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 wit h p = 3 ± ¡ 1 a n d

c = 2 ± =

s
2 p ¡ 1 0 +

µ
± ¡ 7

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
) + ± + 1

2
in Co r o lla r y 2 c a n n o t b e im p r o ve d t o

q
2 p ¡ 1 0 + ( ± ¡ 7

2
) + ± + 1 .

Th e fo llo win g t h e o r e m will b e u s e fu l.
T heor em C: [6 ]. L et G be a 2-connected graph. Then either ( i ) c ¸ p ¡ 1 or ( ii) c ¸ ¾3 ¡ 3
or ( iii ) · = 2 and p ¸ ¾3 ¡ 1 .

2 . P r e lim in a r ie s

Th e fo llo win g le m m a c a n b e p r o ve d b y s t a n d a r d a r g u m e n t s ( c a lle d D ir a c a n d Or e a r g u m e n t s ) .

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 z1; z2 2 V ( P ) and z1 Á z2. If xz; yz 62 E ( G ) for each z 2 V ( z+1

¡!
P z¡2 ) , then

either c = p or p ¸ d( x ) + d( y ) ¡ 2 + jz1
¡!
P z2j.

Th e n e xt le m m a is c r u c ia l fo r t h e p r o o f o f Th e o r e m s 1 a n d 2 .
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 :



M. Koulakzian and Zh. Nikoghosyan 3 3

3 . P r o o fs

P r oof of Lemma 2: L et P = x
¡!
P y be a longest path in G. P ut

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 fo r m m + 1 d i®e r e n t c yc le s t o o b t a in a lo we r

b o u n d fo r t h e c ir c u m fe r e n c e a s t h e m e a n o f t h e ir o r d e r 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 .



3 4 On Longest Cycles in 2-connected Graphs

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

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 . W e c h o o s e L1; L2; :::; Lm s o a s t o m in im iz e m a s we ll
a s b1 a n d bm¡1.

Case 1: m = 2 .
It fo llo ws 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 p =

a1 + a2 + b1 + 1 ¸ d( x ) + d( y ) ¡ 1 + b1, 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 . B y t h e c h o ic e o f L1; L2; L3,

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 ( x) ¡ 2 a n d

c ¸ jQ1j = a1 + a2 + a3 + 3

¸ d( x ) + d( x ) + 1 = d( x ) + d( x ) + m ¡ 2 :
Case 3: m ¸ 4 .
B y t h e c h o ic e o f L1; L2; :::; Lm,

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 :

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

P r oof of T heor em 2: 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) , a g a in c = p.
Case 2: ¾2 + 1 · p · ¾3 ¡ 2 .
If c ¸ ¾3 ¡ 3 , t h e n b y t h e h yp o t h e s is , c ¸ 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 . H e n c e , b y Th e o r e m C, c ¸ p ¡ 1 .



M. Koulakzian and Zh. Nikoghosyan 3 5

Case 3: p ¸ ¾3 ¡ 1 .
S in c e G is 2 -c o n n e c t e d , t h e n b y t h e V in e L e m m a , t h e r e is a vin e fL1; :::; Lmg o n P . B y

Th e o r e m 1 , 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 + 1
4
( ¾2 ¡ 7 ) 2 +

1

2
( ¾2 + 1 ) :

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

Refer ences

[1 ] J.A . B o n d y, \ L a r g e c yc le s in g r a p h s " , D iscrete M ath., vo l. 1 , p p . 1 2 1 -1 3 1 , 1 9 7 1 .

[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 ] J. C. B e r m o n d , \ On H a m ilt o n ia n wa lks " , Congr Numer, vo l. 1 5 , p p . 4 1 -5 1 , 1 9 7 6 .

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

[5 ] N . L in ia l, \ A lo we r b o u n d o n t h e c ir c u m fe r e n c e o f a g r a p h " , D iscrete M ath., vo l. 1 5 ,
p p . 2 9 7 -3 0 0 , 1 9 7 6 .

[6 ] 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.10.2016, accepted 17.01.2017.

2-ϳå³Ïóí³Í ·ñ³ýÝ»ñÇ ³Ù»Ý³»ñϳñ óÇÏÉ»ñÇ Ù³ëÇÝ

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

²Ù÷á÷áõÙ

¸Çóáõù n-Á Ý߳ݳÏáõÙ ¿ G ·ñ³ýÇ ·³·³ÃÝ»ñÇ ù³Ý³ÏÁ, c-Ý G-Ç` ³Ù»Ý³»ñϳñ óÇÏÉÇ
»ñϳñáõÃÛáõÝÁ, p-Ý` ³Ù»Ý³»ñϳñ ßÕóÛÇ ·³·³ÃÝ»ñÇ ù³Ý³ÏÁ ¨ ±-Ý` ·ñ³ýÇ Ýí³½³·áõÛÝ
³ëïÇ׳ÝÁ: 1952-ÇÝ ¸Çñ³ÏÁ ³å³óáõó»ó, áñ (i) »Ã» G-Ý 2-ϳå³Ïóí³Í ·ñ³ý ¿, ³å³
c ¸ m in fn; 2 ±g: ¸Çñ³ÏÇ 2 ± Ý»ñùÇÝ ·Ý³Ñ³ï³Ï³ÝÁ Çñ³ñÇó ³ÝÏ³Ë ÁݹɳÛÝ»óÇÝ ´áݹÇÝ
(1971), ´»ñÙáݹÁ ¨ ÈÇÝdzÉÁ (1976), û·ï³·áñÍ»Éáí ¾2 (áã ѳñ¨³Ý »ñÏáõ ·³·³ÃÝ»ñÇ
³ëïÇ׳ÝÝ»ñÇ Ýí³½³·áõÛÝ ·áõÙ³ñÁ) å³ñ³Ù»ïñÁ, (ii) »Ã» G-Ý 2-ϳå³Ïóí³Í ·ñ³ý
¿, ³å³ c ¸ m in fn; ¾2g: Ü»ñϳ ³ß˳ï³ÝùáõÙ (i) ¨ (ii) ÁݹɳÛÝáõÙÝ»ñÁ ³í»ÉÇ »Ý
ÁݹɳÛÝíáõÙ` ·Ý³Ñ³ï³Ï³ÝÝ»ñÇ Ù»ç Ý»ñÙáõÍ»Éáí p-Ý ¨ G ·ñ³ýÇ ³Ù»Ý³»ñϳñ ßÕóÛÇ
µ³Õ»ÕÇ »ñϳñáõÃÛáõÝÁ áñå»ë Ýáñ å³ñ³Ù»ïñ»ñ n, ±, ¾2 å³ñ³Ù»ïñ»ñÇ ÏáÕùÇÝ:



3 6 On Longest Cycles in 2-connected Graphs

Î äëèííåéøèõ öèêëàõ 2-ñâÿçíûõ ãðàôîâ
Ì. Êóëàêçÿí è Æ. Íèêîãîñÿàí

Àííîòàöèÿ

Ïóñòü n, c, p è ± îáîçíà÷àþò ÷èñëî âåðøèí ãðàôà G, äëèíà äëèííåéøåãî
öèêëà, ÷èñëî âåðøèí äëèííåéøåé öåïè è ìèíèìàëüíàÿ ñòåïåíü ãðàôà.  1952
ãîäó Äèðàê äîêàçàë, ÷òî (i) åñëè G ÿâëÿåòñÿ 2-ñâÿçíûì ãðàôîì, òî c ¸ m in fn; 2 ±g:
Ýòó îöåíêó íåçàâèñèìî ðàñøèðèëè Áîíäè (1971), Áåðìîíä è Ëèíèàë (1976) ñ
ïîìîùüþ ïàðàìåòðà ¾2 (ìèíèìàëüíàÿ ñóììà ñòåïåíåé äâóõ íå ñîñåäíèõ âåðøèí):
(ii) åñëè G ÿâëÿåòñÿ 2-ñâÿçíûì ãðàôîì, òî c ¸ m in fn; ¾2g. Â íàñòîÿùåé ðàáîòå
ïðåäñòàâëåíû äâå íîâûå ðàñøèðåíèÿ îöåíîê (i) è (ii) ïîìîùüþ ïàðàìåòðîâ p è
äëèíû ïëþùà äëèííåéøåé öåïè ãðàôà G íà ðÿäó ñ ïàðàìåòðàìè n, ±, ¾2.