2_Mossine-myu_18-25.DVI


Mathematical Problems of Computer Science 49, 18{25, 2018.

T wo Gener alized Lower B ounds for the Cir cumfer ence

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

In 2013, the second author obtained two lower bounds for the length of a longest
cycle C in a graph G in terms of the length of a longest path (a longest cycle) in G ¡C
and the minimum degree of G (Zh.G. Nikoghosyan, "Advanced Lower Bounds for the
Circumference", Graphs and Combinatorics 29, pp. 1531-1541, 2013). In this paper
we present two analogous bounds based on the average of the ¯rst i smallest degrees
in G ¡ C for appropriate i instead of the minimum degree.

Keywords: Circumference, Minimum degree, Degree sums.

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

L e t c b e t h e c ir c u m fe r e n c e - t h e le n g t h o f a lo n g e s t c yc le o f a g r a p h G a n d ± t h e m in im u m
d e g r e e in G.

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 r e s u lt s .

T heor em 1. L et C be a longest cycle in a graph G, p̂ the order of a longest path in G ¡ C
and ¹ the average of the ¯rst p̂ smallest degrees in G ¡ C. Then

c ¸ ( p̂ + 1 ) ( ¹ ¡ p̂ + 1 ) :

T heor em 2. L et C be a longest cycle in a graph G, ĉ the order of a longest cycle in G ¡ C
and ¹ the average of the ¯rst ĉ smallest degrees in G ¡ C. Then

c ¸ ( ĉ + 1 ) ( ¹ ¡ ĉ + 1 ) :

Ob s e r vin g t h a t ¹ ¸ ± in Th e o r e m s 1 a n d 2 , we o b t a in t h e o r ig in a l lo we r b o u n d s [2 ] a s
im m e d ia t e c o r o lla r ie s in t e r m s o f p̂, ĉ a n d ±.

T heor em A [2 ]. L et C be a longest cycle in a graph G and p̂ the order of a longest path in
G ¡ C. Then

c ¸ ( p̂ + 1 ) ( ± ¡ p̂ + 1 ) :
T heor em B [2 ]. L et C be a longest cycle in a graph G and ĉ the order of a longest path in
G ¡ C. Then

c ¸ ( ĉ + 1 ) ( ± ¡ ĉ + 1 ) :

1 8



M. Koulakzian and Zh. Nikoghosyan 1 9

2 . D e ¯ n it io n s

W e u s e B o n d y a n d Mu r t y [1 ] fo r t e r m in o lo g y a n d n o t a t io n n o t d e ¯ n e d h e r e , a n d 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 o u t lo o p s a n d m u lt ip le e d g e s . Th e ve r t e x s e t o f a g r a p h G
is d e n o t e d b y V ( G) o r ju s t V ; t h e s e t o f e d g e s b y E ( G) o r ju s t E. Fo r a s u b g r a p h H o f G
we a ls o u s e G ¡ H s h o r t fo r G ¡ V ( H ) , a n d jHj s h o r t fo r jV ( H ) j.

P a t h s a n d c yc le s in G c a n b e c o n s id e r e d a s c o n n e c t e d s u b g r a p h s o f G, h a vin g a m a xim u m
d e g r e e 0 ,1 o r 2 . Th e le n g t h o f a p a t h P a n d o f a c yc le Q, d e n o t e d b y l ( P ) a n d l ( Q ) , is
jV ( P ) j ¡ 1 a n d jV ( Q ) j, r e s p e c t ive ly. W e d e n o t e l ( P ) = ¡ 1 a n d l ( Q ) = 0 if a n d o n ly if
V ( P ) = V ( Q ) = ;. A g r a p h is s a id t o b e H a m ilt o n ia n if it s lo n g e s t c yc le p a s s e s t h r o u g h a ll
o f it s ve r t ic e s . Th e ve r t ic e s a n d e d g e s in G c a n b e in t e r p r e t e d a s c yc le s o f le n g t h s 1 a n d 2 ,
r e s p e c t ive ly.

A n ( x; y ) -p a t h is a p a t h wit h e n d ve r t ic e s x a n d y. Give n a n ( x; y ) -p a t h L o f G we d e n o t e

b y
¡!
L t h e p a t h L wit h a n o r ie n t a t io n fr o m x t o y. If u; v 2 V ( L) t h e n u¡!L v d e n o t e s t h e

c o n s e c u t ive ve r t ic e s o n
¡!
L fr o m u t o v in t h e d ir e c t io n s p e c ī e d b y

¡!
L . Th e s a m e ve r t ic e s , in

r e ve r s e o r d e r , a r e g ive n b y v
á
L u. Fo r L = x

¡!
L y a n d u 2 V ( L) , le t u+ ( ¡!L ) ( o r ju s t u+ ) d e n o t e

t h e s u c c e s s o r o f u ( u 6= y ) o n ¡!L a n d u¡ d e n o t e it s p r e d e c e s s o r ( u 6= x ) . If A µ V ( L) ¡ y
a n d B µ V ( L) ¡ x, t h e n we d e n o t e A+ = fv+jv 2 Ag a n d B¡ = fv¡jv 2 Bg. A s im ila r
n o t a t io n is u s e d fo r t h e c yc le s . If Q is a c yc le a n d u 2 V ( Q ) , t h e n u¡!Q u = u. Fo r v 2 V ,
p u t N ( v ) = fu 2 V juv 2 Eg, d( v ) = jN ( v ) j a n d ± = m in fd( u ) ju 2 V g.

3 . S p e c ia l D e ¯ n it io n s

Fo r t h e r e m a in d e r o f t h is s e c t io n , le t a s u b g r a p h F o f a g r a p h G a n d a p a t h ( o r a c yc le )
¡!
M

in G ¡ F b e ¯ xe d .

De¯nition 1. ( ¤i) -m in im a lit y, ( ¤i) -m a xim a lit y.

W e u s e t h e n o t io n s o f ( ¤i ) -m in im a lit y a n d ( ¤i ) -m a xim a liy d e ¯ n e d wit h r e s p e c t t o c e r t a in
o p e r a t io n s fo r i = 1 ; 2 ; :::; 1 0 . Th e y will b e d e s c r ib e d in d e t a il c u r r e n t ly.

De¯nition 2. MF -extension;
¡!
T ( u) ; _u; Äu.

Fo r e a c h u 2 V ( M ) , le t ¡!T ( u ) = u¡!T ( u ) Äu b e a p a t h in G, h a vin g o n ly u in c o m m o n
wit h V ( M ) . If V ( T ( u) ) \ V ( T ( v ) ) = ; a n d V ( T ( u ) ) µ V ( G ¡ F ) fo r a ll d is t in c t ve r t ic e s
u; v 2 V ( M ) , t h e n t h e fo r e s t T , d e ¯ n e d b y fT ( u ) ju 2 V ( M ) g, is s a id t o b e MF -e xt e n s io n .
If Äu 6= u fo r s o m e u 2 V ( M ) , t h e n we u s e _u t o d e n o t e u+ ( ¡!T ( u) ) .

De¯nition 3. ©u; '( u ) ; ª( u ) ; Ã ( u ) .

L e t T b e a n M F -e xt e n s io n . Fo r e a c h u 2 V ( M ) , p u t
©u = N ( Äu) \ V ( T ) ; 'u = j©uj;
ªu = N ( Äu ) \ V ( F ) ; Ãu = jªuj:

De¯nition 4. U0; U 0; U1; U
¤.



2 0 Two Generalized Lower Bounds for the Circumference

L e t T b e a n MF -e xt e n s io n . P u t

U0 = fu 2 V ( M ) ju = Äug; U 0 = V ( M ) ¡ U0;

U ¤ = fu 2 U 0j©u µ V ( T ( u ) ) g; U1 = V ( M ) ¡ ( U0 [ U¤ ) :

De¯nition 5. M aximal M F -extension.

A n MF -e xt e n s io n T is s a id t o b e m a xim a l if it is e xt r e m a l wit h r e s p e c t t o t h e fo llo win g
o p e r a t io n : - if t h e r e e xis t s a n e d g e Äuz s u c h t h a t u 2 V ( M ) a n d z 62 V ( T ) [ V ( F ) , t h e n
r e p la c in g T ( u ) b y uT ( u) Äuz, we o b t a in a n e w M F -e xt e n s io n T 0 wit h jV ( T 0 ) j > jV ( T ) j.

De¯nition 6. ( U0 ) -minimal and ( U0; U
¤ ) -minimal M F -extensions.

A n MF -e xt e n s io n T is s a id t o b e ( U0 ) -m in im a l, if it is c h o s e n s u c h t h a t U0 is ( ¤ 6 ) -m in im a l
( s e e t h e p r o o f o f Th e o r e m 1 ) . A ( U0 ) -m in im a l MF -e xt e n s io n T is s a id t o b e ( U0; U

¤ ) -m in im a l
if it is c h o s e n s u c h t h a t U ¤ is ( ¤1 0 ) -m in im a l ( s e e t h e p r o o f o f Th e o r e m 2 ) .

De¯nition 7. Bu; B
¤
u; bu; b

¤
u.

L e t T b e a n MF -e xt e n s io n a n d u 2 V ( M ) . P u t Bu = fv 2 U0jv _u 2 Eg a n d bu = jBuj.
B y t h e d e ¯ n it io n , Bu = ; fo r e a c h u 2 U0. Fu r t h e r m o r e , fo r e a c h u 2 U0 , le t
B¤u = fv 2 U 0ju _v 2 Eg a n d jB¤uj = b¤u.

4 . P r e lim in a r ie s

Th e p r o o fs o f t h e fo llo win g le m m a s c a n b e ¯ n d in [2 ].

Lemma 1. L et C be a cycle in a graph G and P a path in G¡C. L et ¡!P 0; :::;
¡!
P p be pairwise

disjoint paths in G ¡ C with ¡!P i = vi
¡!
P iwi ( i = 0 ; 1 ; :::; p ) , having only v0; :::; vp in common

with P . Then either there is a cycle in G longer than C or

jCj ¸
pX

i=0

jZij +
¯̄
¯̄
¯

p[

i=0

Zi

¯̄
¯̄
¯ ;

where Zi = N ( wi ) \ V ( C ) ( i = 0 ; 1 ; :::; p ) .

Lemma 2. L et F be a subgraph of a graph G and R a longest cycle in G ¡ F with a ( U0 ) -
minimal RF -extension T . Then either there is a cycle longer than R or l ( R) ¸ 'u + bu + 1
for each u 2 U1.

Lemma 3. L et F be a subgraph of a graph G and P a path in G¡F with a ( U0 ) -minimal P F -
extension T . Then either there is a path longer than P or l ( P ) ¸ 'u+bu for each u 2 U1[U¤.



M. Koulakzian and Zh. Nikoghosyan 2 1

5 . P r o o fs

P r oof of T heor em 1. L et Q = u0:::uq be a path in G ¡ C with a ( U0 ) - minimal QC-
extension T . Assume without loss of generality that C is ( ¤ 1 ¡ ¤ 4 ) -extremal, and Q is
( ¤ 7 ¡ ¤ 9 ) -extremal. Since G is non-Hamiltonian, we have q ¸ 0 .

Claim 1. If u 2 U0 a n d v 2 U 0, t h e n ©u \ V ( T ( v ) ) µ fv; _vg.
P r oof. S u p p o s e o t h e r wis e . L e t z 2 V ( T ( v ) ) ¡ fv; _vg. Th e n , r e p la c in g T ( u ) a n d T ( v ) b y
uz

¡!
T ( v ) Äv a n d v

¡!
T ( v ) z¡, r e s p e c t ive ly, we c a n fo r m ( d e n o t e t h is o p e r a t io n b y ( ¤ 6 ) ) a n e w

QC-e xt e n s io n , c o n t r a d ic t in g t h e ( U0 ) - m in im a lit y o f T . 2

Claim 2. If u 2 U0, t h e n 'u · q + b¤u.
P r oof. Th e p r o o f fo llo ws im m e d ia t e ly fr o m D e ¯ n it io n s 3 , 7 a n d Cla im 1 . 2

Claim 3. If u 2 U 0, t h e n 'u · q ¡ bu.
P r oof. U s in g L e m m a 3 wit h t h e fa c t t h a t Q is ( ¤ 7 ¡ ¤9 ) -e xt r e m a l, we o b t a in q ¸ 'u + bu
fo r e a c h u 2 U 0, a n d t h e r e s u lt fo llo ws . 2

Ob s e r vin g t h a t X

u2U0
b¤u =

X

u2U 0
bu

( b y t h e d e ¯ n it io n ) a n d u s in g Cla im s 2 a n d 3 , we o b t a in

qX

i=0

'ui · q ( q + 1 ) +
X

u2U0
b¤u ¡

X

u2U 0
bu = q ( q + 1 ) :

S u p p o s e ¯ r s t t h a t 'ui + Ãui 6= d( Äui ) fo r s o m e i 2 0 ; q. Th e n t h e r e e xis t s a n e d g e Äuz s u c h
t h a t z 62 V ( T ) [ V ( C ) . A d d in g Äuz t o T we o b t a in a n e w QC-e xt e n s io n , c o n t r a d ic t in g t h e
m a xim a lit y o f T ( D e ¯ n it io n 5 ) . N o w le t 'ui + Ãui = d( Äui ) ( i = 0 ; :::; q ) . Th e n

qX

i=0

Ãui =
qX

i=0

d( Äui ) ¡
qX

i=0

'ui ¸
qX

i=0

d( Äui ) ¡ q ( q + 1 ) :

It fo llo ws , in p a r t ic u la r , t h a t

m a x
i

fÃuig ¸
1

q + 1

qX

i=0

Ãui ¸
1

q + 1

qX

i=0

d ( Äui ) ¡ q:

B y L e m m a 1 ,

c ¸
qX

i=0

Ãui + m a x
i

fÃuig

¸ ( q + 2 )
Ã

1

q + 1

qX

i=0

d( Äui ) ¡ q
!
¸ ( q + 2 ) ( ¹q ¡ q ) :

P r oof of T heor em 2. L e t H = u1:::uku1 b e a c yc le in G ¡ C wit h a n ( U0; U ¤ ) -m in im a l
HC-e xt e n s io n T . L e t H b e ( ¤5 ) -e xt r e m a l. P u t

U¤1 =

(
u 2 U¤j'u ·

h

2

)
; U¤2 =

(
u 2 U¤j'u ¸

h + 1

2

)
:



2 2 Two Generalized Lower Bounds for the Circumference

Claim 1. If u 2 U0 a n d v 2 U 0, t h e n ©u \ V ( T ( v ) ) µ fv; _vg.
P r oof. Th e p r o o f is ve r y s im ila r t o t h a t o f Cla im 1 in Th e o r e m 1 . 2

Claim 2. If u 2 U0, t h e n 'u · h ¡ 1 + b¤u.
P r oof. Im m e d ia t e fr o m D e ¯ n it io n s 3 , 7 a n d Cla im 1 . 2

Claim 3. If u 2 U1, t h e n 'u · h ¡ 1 ¡ bu.
P r oof. S in c e H is ( ¤ 5 ) -e xt r e m a l, b y L e m m a 2 , h ¸ 'u + bu + 1 fo r e a c h u 2 U1, a n d t h e
r e s u lt fo llo ws . 2

Claim 4. If u 2 U¤, t h e n 'u · h ¡ 1 ¡ bu + 'u ¡ h2 .
P r oof. S in c e H is ( ¤ 5 ) -e xt r e m a l, b y t h e s t a n d a r d a r g u m e n t s , h ¸ 2 ( bu + 1 ) fo r e a c h u 2 U¤,
a n d t h e r e s u lt fo llo ws im m e d ia t e ly. 2

Claim 5. If u 2 U1, t h e n 'u · h ¡ 1 ¡ bu.
P r oof. Im m e d ia t e fr o m Cla im s 3 a n d 4 . 2

If U¤2 = ;, t h e n b y Cla im s 2 a n d 5 ,
P

u 'u · h( h ¡ 1 ) . B u t t h e n , a s in Th e o r e m 1 ,
c ¸ ( h + 1 ) ( ¸1 ¡ h + 1 ) , wh e r e ¸1 = 1h

Pk
i=1 d( Äui ) ¸ ¹h. N o w le t U¤2 6= ;. Ch o o s e v 2 U ¤2 s u c h

t h a t

'v = m a x
u2U¤

2

f'ug: ( 1 )

Claim 6. If u 2 U¤2 , t h e n 'u · h ¡ 1 ¡ bu + 'v ¡ h2 .
P r oof. Im m e d ia t e fr o m ( 1 ) a n d Cla im 4 . 2

U s in g Cla im s 2 , 5 , 6 a n d r e c a llin g t h a t
P

u2U0 b
¤
u =

P
u2U 0 bu a n d jU0j+jU1[U

¤
1 j+jU¤2 j = h,

we g e t
X

u

'u =
X

u2U0
'u +

X

u2U1[U ¤1
'u +

X

u2U ¤2
'u · h( h ¡ 1 ) + jU ¤2 j

Ã
'v ¡

h

2

!
: ( 2 )

B y D e ¯ n it io n 3 , ©v µ V ( T ( v ) ) . L e t v1; :::; vt b e t h e e le m e n t s o f ©+v , o c c u r r in g o n
¡!
T ( v )

in a c o n s e c u t ive o r d e r wit h vt = Äv. Cle a r ly t = j©vj = 'v. P u t

N ( vi ) \ V ( T ) = ©0i; N ( vi ) \ V ( C ) = Z0i ( i = 1 ; :::; t) : ( 3 )

If ©0i \ ( V ( T ) ¡ V ( T ( v ) ) ) 6= ; fo r s o m e i 2 1 ; t, t h e n r e p la c in g T ( v ) b y

v
¡!
T ( v ) v¡i Äv

á
T ( v ) vi;

we fo r m ( d e n o t e t h is o p e r a t io n b y ( ¤ 1 0 ) ) a n e w HC-e xt e n s io n , c o n t r a d ic t in g t h e m in im a lit y
o f jU¤j. S o , we c a n a s s u m e ©0i µ V ( T ( v ) ) ( i = 1 ; :::; t) . A s s u m e w.l.o .g . t h a t m a xi j©0ij =
j©0tj = 'v. S o ,

m a x
i

j©0ij = j©0tj = j©vj = 'v = t: ( 4 )

S in c e Ãui = d ( ui ) ¡ 'ui ( i = 1 ; :::; h) a n d jZ0ij = d ( vi ) ¡ j©0ij ( i = 1 ; :::; t ¡ 1 ) , we h a ve
hX

i=1

Ãui +
t¡1X

i=1

jZ0ij =
hX

i=1

( d( ui ) ¡ 'ui ) +
t¡1X

i=1

( d( vi ) ¡ j©0ij)



M. Koulakzian and Zh. Nikoghosyan 2 3

=
hX

i=1

d( ui ) +
t¡1X

i=1

d( vi ) ¡
hX

i=1

'ui ¡
t¡1X

i=1

j©0ij: ( 5 )

P u t

¸2 =
1

h + t ¡ 1

Ã
hX

i=1

d( ui ) +
t¡1X

i=1

d ( vi )

!
¸ ¸1 ¸ ¹h:

Case 1. jU ¤2 j = 1 .
B y ( 2 ) , ( 4 ) a n d ( 5 ) ,

hX

i=1

Ãui +
t¡1X

i=1

jZ0ij ¸ ( h + t ¡ 1 ) ¸2 ¡ h ( h ¡ 1 ) ¡ t +
h

2
¡

t¡1X

i=1

t

= ( h + t ¡ 1 ) ¸2 ¡ h2 ¡ t2 +
3 h

2
:

It fo llo ws , in p a r t ic u la r , t h a t

m a x
i

fÃui ; jZ0ijg ¸ ¸2 ¡
h2 + t2 ¡ 3h

2

h + t ¡ 1 ¸ ¸2 ¡
3 h

2
+ 2 :

If ¸2 · h ¡ 1 , t h e n c le a r ly c ¸ ( h + 1 ) ( ¸2 ¡ h + 1 ) . L e t ¸2 ¸ h ¸ t + 1 . A p p lyin g L e m m a 1
t o Q = Äv

á
T ( v ) v

¡!
H v¡, we g e t

c ¸
hX

i=1

Ãui +
t¡1X

i=1

jZ0ij + m a x
i

fÃui ; jZ0ijg

¸ ( h + 1 ) ( ¸2 ¡ h + 1 ) + ( t ¡ 1 ) ( ¸2 ¡ t ¡ 1 ) ¸ ( h + 1 ) ( ¸2 ¡ h + 1 ) :
Case 2. jU ¤2 j ¸ 2 .
Ch o o s e w 2 U ¤2 ¡ v s u c h t h a t 'v ¸ 'w ¸ 'u fo r e a c h u 2 U ¤2 ¡ fv; wg. D e ¯ n e wi; Z00i ; ©00i
( i = 1 ; :::; r ) fo r T ( w ) in t h e s a m e wa y a s vi; Z

0
i a n d ©

0
i we r e d e ¯ n e d fo r T ( v ) . A s in ( 4 ) , we

c a n a s s u m e w.l.o .g . t h a t m a xi j©00i j = j©00rj = j©wj = 'w = r. Cle a r ly, t+r = 'v +'w ¸ h+ 1 .
Th e n

tX

i=1

jZ0ij +
rX

i=1

jZ00i j =
tX

i=1

( d( vi ) ¡ j©0ij) +
rX

i=1

( d ( wi ) ¡ j©00i j )

=
tX

i=1

d ( vi ) +
rX

i=1

d( wi ) ¡
tX

i=1

j©0ij ¡
rX

i=1

j©00i j ¸ ( t + r ) ¸3 ¡ t2 ¡ r2;

wh e r e

¸3 =
1

t + r

Ã
tX

i=1

d( vi ) +
rX

i=1

d( wi )

!
¸ ¹h:

In p a r t ic u la r ,

m a x
i

fjZ0ij; jZ00i jg ¸ ¸3 ¡
t2 + r2

t + r
:

A p p lyin g L e m m a 1 t o Q = Äv
á
T ( v ) v

¡!
H w

¡!
T ( w ) Äw, we g e t

c ¸
tX

i=1

jZ0ij +
rX

i=1

jZ00i j + m a x
i

fjZ0ij; jZ00i jg ¸ ( t + r ) ¸3 ¡ t2 ¡ r2 + ¸3 ¡
t2 + r2

t + r



2 4 Two Generalized Lower Bounds for the Circumference

¸ ( h + 1 ) ( ¸3 ¡ h + 1 ) + ¸3 ( t + r ¡ h) + h2 ¡ 1 ¡ t2 ¡ r2 ¡
t2 + r2

t + r
:

If ¸3 · h ¡ 1 , t h e n c le a r ly, c ¸ ( h + 1 ) ( ¸3 ¡ h + 1 ) . Ot h e r wis e ,

c ¸ ( h + 1 ) ( ¸3 ¡ h + 1 ) + h( t + r ) ¡ 1 ¡ t2 ¡ r2 ¡
t2 + r2

t + r

¸ ( h + 1 ) ( ¸3 ¡ h + 1 ) + ( h ¡ 1 ) ( t + r ) ¡ t2 ¡ r2:
Ob s e r vin g t h a t

h ¡ 1 ¸ m a xft; rg ¸ t
2 + r2

t + r
;

we o b t a in c ¸ ( h+1 ) ( ¸3¡h+1 ) . Th u s , c ¸ ( h+1 ) ( ¸¡h+1 ) , wh e r e ¸ = m in f¸1; ¸2; ¸3g ¸ ¹h.

Refer ences

[1 ] J.A . B o n d y a n d U .S .R . Mu r t y, Gr a p h Th e o r y wit h A p p lic a t io n s . 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 ] Zh .G. N iko g h o s ya n , \ A d va n c e d 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 " , Gr a p h s a n d Co m -
b in a t o r ic s 2 9 , p p . 1 5 3 1 -1 5 4 1 , 2 0 1 3 .

Submitted 22.08.2017, accepted 24.12.2017.

¶ñ³ýÇ ³Ù»Ý³»ñϳñ óÇÏÉÇ »ñϳñáõÃÛ³Ý
»ñÏáõ ÁݹѳÝñ³óí³Í ·Ý³Ñ³ï³Ï³ÝÝ»ñ

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

²Ù÷á÷áõÙ

2013-ÇÝ »ñÏñáñá¹ Ñ»ÕÇݳÏÁ G ·ñ³ýÇ ³Ù»Ý³»ñϳñ C óÇÏÉÇ »ñϳñáõÃÛ³Ý Ñ³Ù³ñ
ëï³ó³í »ñÏáõ ëïáñÇÝ ·Ý³Ñ³ï³Ï³ÝÝ»ñ` ³ñï³Ñ³Ûïí³Í G ¡ C-Ç ³Ù»Ý³»ñϳñ
ßÕóÛÇ »ñϳñáõÃÛ³Ý (³Ù»Ý³»ñϳñ óÇÏÉÇ »ñϳñáõÃÛ³Ý) ¨ G ·ñ³ýÇ Ýí³½³·áõÛÝ
³ëïÇ׳ÝÇ µÝáõó·ñÇãÝ»ñáí (Zh.G. Nikoghosyan, Advanced Lower Bounds for the Cir-
cumference, Graphs and Combinatorics 29, pp. 1531-1541, 2013): Ü»ñϳ ³ß˳ï³ÝùáõÙ
Ý»ñϳ۳óíáõÙ »Ý »ñÏáõ ѳٳÝÙ³Ý ·Ý³Ñ³ï³Ï³ÝÝ»ñ, áñï»Õ Ýí³½³·áõÛÝ ³ëïÇ׳ÝÇ
µÝáõó·ñÇãÁ ÷á˳ñÇÝí³Í ¿ G¡C-Ç ·³·³ÃÝ»ñÇ ³é³çÇÝ i ³Ù»Ý³÷áùñ ³ëïÇ׳ÝÝ»ñÇ
ÙÇçÇÝ Ãí³µ³Ý³Ï³Ýáí G ¡ C-áí å³Ûٳݳíáñí³Í áñáß i å³ñ³Ù»ïñÇ Ñ³Ù³ñ:



M. Koulakzian and Zh. Nikoghosyan 2 5

Äâå îáîáùåííûå íèæíèå îöåíêè äëÿ äëèíû
äëèííåéøåãî öèêëà ãðàôà

Ì. Êóëàêçÿí è Æ. Íèêîãîñÿí

Àííîòàöèÿ

 2013 ãîäó âòîðîé àâòîð ïîëó÷èë äâå íèæíèå îöåíêè äëÿ äëèíû äëèííåéøåãî
öèêëà ãðàôà G âûðàæåííûå ÷åðåç äëèíó äëèííåéøåé öåïè (äëèííåéøåãî
öèêëà) ïîäãðàôà G ¡ C è ìèíèìàëüíóþ ñòåïåíü ãðàôà G (Zh.G. Nikoghosyan,
Advanced Lower Bounds for the Circumference, Graphs and Combinatorics 29,
pp. 1531-1541, 2013)? Â íàñòîÿùåé ðàáîòå ïðåäñòàâëÿþòñÿ äâå îáîáùåííûå
àíàëîãè÷íûå îöåíêè, ãäå âìåñòî ìèíèìàëüíîé ñòåïåíè ðàññìàòðèâàåòñÿ ñðåäíÿÿ
àðèôìåòè÷åñêàÿ ñòåïåíåé ïåðâûõ i íàèìåíüøèõ ñòåïåíåé âåðøèí ïîäãðàôà
G ¡ C äëÿ ïîäõîäÿùåãî ïàðàìåòðà i.