D:\Sbornik_45_TeX\...\Nik.DVI


Mathematical Problems of Computer Science 45, 19{26, 2016.

On Some Ver sions of Conjectur es of B ondy and Jung

Zh o r a G. N iko g h o s ya n ¤

Institute for Informatics and Automation Problems of NAS RA

e-mail: zhora@ipia.sci.am

Abstract

Most known fundamental theorems in hamiltonian graph theory (due to Dirac,
Ore, Nash-Williams, Bondy, Jung and so on) are related to the length of a longest
cycle C in a graph G in terms of connectivity · and the length p of a longest path in
G ¡ C, for the special cases when · · 3 and p · 1 (if p = ¡1 then V (G ¡ C) = ;
and C is called hamiltonian; and if p = 0 then V (G ¡ C) is an independent set of
vertices and C is called dominating). Bondy (1980) and Jung (2001) conjectured a
common generalization of these results in terms of degree sums including p and · as
parameters. These conjectures still are open in the original form. In 2009, the minimum
degree c¡versions (c - the length of a longest cycle in V (G ¡ C)) of Conjectures of
Bondy and Jung are shown to be true by the author (Discrete Math, v.309, 2009, 1925-
1930). In this paper, using another result of the author (Graphs and Combinatorics,
v.29, 2013, 1531-1541), a number of analogous sharp results are presented including
both p and c¡minimum degree versions of Conjectures of Bondy and Jung without
connectivity conditions, inspiring a number of new strengthened and extended versions
of conjectures of Bondy and Jung.

Keywords: Hamilton cycle, Dominating cycle, Long cycles, Bondy's conjecture,
Jung's Conjecture.

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

Th e g e n e r a liz e d c o n je c t u r e s o f B o n d y [1 ] ( 1 9 8 0 ) a n d Ju n g [2 ] ( 2 0 0 1 ) in c lu d e a n u m b e r o f
m o s t kn o wn fu n d a m e n t a l r e s u lt s ( t h e m in im u m d e g r e e a n d t h e d e g r e e s u m ve r s io n s ) in
h a m ilt o n ia n g r a p h t h e o r y c o n c e r n in g H a m ilt o n a n d d o m in a t in g c yc le s a s s p e c ia l c a s e s d u e
t o D ir a c [3 ], Or e [4 ], N a s h -W illia m s [5 ], B o n d y [6 ],[1 ] Ju n g [7 ],[8 ],[9 ] a n d s o o n . Th e s e
c o n je c t u r e s s t ill a r e o p e n in t h e o r ig in a l fo r m . U s in g s o m e e a r lie r r e s u lt s o f t h e a u t h o r [1 0 ],
[1 1 ] ( 2 0 0 9 , 2 0 1 3 ) , in t h is p a p e r s o m e ve r s io n s o f c o n je c t u r e s o f B o n d y a n d Ju n g a r e s h o wn t o
b e t r u e , in s p ir in g a n u m b e r o f n e w s t r e n g t h e n e d a n d e xt e n d e d ve r s io n s o f t h e s e c o n je c t u r e s .
A ll r e s u lt s a r e s h a r p .

Th r o u g h o u t t h is a r t ic le we 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 o r m u l-
t 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 2 ].

Th e s e t o f e d g e s o f a g r a p h G is d e n o t e d b y E ( G ) . 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 jQj, is jE ( Q) j. E a c h ve r t e x a n d e d g e in G c a n b e in t e r p r e t e d a s
s im p le 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. Fo r a lo n g e s t c yc le C in G, le t p a n d c d e n o t e
t h e le n g t h s o f a lo n g e s t p a t h a n d a lo n g e s t c yc le in GnC, r e s p e c t ive ly. P u t p = ¡ 1 wh e n

1 9



2 0 On Some Versions of Conjectures of Bondy and Jung

V ( GnC ) = ;. If e it h e r p = ¡ 1 o r c = 0 , t h e n C is c a lle d a H a m ilt o n c yc le . N e xt , if e it h e r
p = 0 o r c = 1 , t h e n C is c a lle d a d o m in a t in g c yc le . Fu r t h e r , if c · ¸ ¡ 1 fo r a n in t e g e r
¸, t h e n C is c a lle d a CD¸ ( c yc le d o m in a t in g ) -c yc le . In p a r t ic u la r , CD1-c yc le s a r e H a m ilt o n
c yc le s a n d CD2-c yc le s a r e d o m in a t in g c yc le s .

L e t G b e a g r a p h o f o r d e r n a n d m in im u m d e g r e e ±. Th e d e g r e e s u m o f s s m a lle s t d e g r e e s
a m o n g s p a ir wis e n o n a d ja c e n t ve r t ic e s will b e d e n o t e d b y ¾s.

In 1 9 8 0 , B o n d y [1 ] c o n je c t u r e d a c o m m o n g e n e r a liz a t io n o f we ll-kn o wn t h e o r e m s o f Or e
[4 ] ( 1 9 6 0 , ¸ = 1 ) a n d B o n d y [1 ] ( 1 9 8 0 , ¸ = 2 ) in t e r m s o f p.

Conjectur e A: [1 ]. L et G be a ¸-connected ( ¸ ¸ 1 ) graph and C a longest cycle in G. If

1

¸ + 1
¾¸+1 ¸

n + 2

¸ + 1
+ ¸ ¡ 2 ;

then p · ¸ ¡ 2 .

Fo r ¸ = 3 , Co n je c t u r e A h a s b e e n ve r ī e d in 1 9 8 7 b y Zo u [1 3 ].
Th e m in im u m d e g r e e ve r s io n o f Co n je c t u r e A c o n t a in s t wo fu n d a m e n t a l t h e o r e m s o n t h is

s u b je c t d u e t o D ir a c [3 ] ( 1 9 5 2 , ¸ = 1 ) a n d N a s h -W illia m s [5 ] ( 1 9 7 1 , ¸ = 2 ) a s s p e c ia l c a s e s .

Conjectur e B : [1 ]. L et G be a ¸-connected ( ¸ ¸ 1 ) graph and C a longest cycle in G. If

± ¸ n + 2
¸ + 1

+ ¸ ¡ 2 ;

then p · ¸ ¡ 2 .

Fo r ¸ = 3 , Co n je c t u r e B h a s b e e n ve r ī e d in 1 9 8 1 b y Ju n g [9 ].
In 2 0 0 9 , t h e a u t h o r p r o ve d [1 0 ] t h a t e a c h lo n g e s t c yc le in G u n d e r t h e c o n d it io n o f Co n -

je c t u r e B , is a CDm in f¸;±¡¸+1g-c yc le .

T heor em A: [1 0 ]. L et G be a ¸-connected ( ¸ ¸ 1 ) graph and C a longest cycle in G. If

± ¸ n + 2
¸ + 1

+ ¸ ¡ 2 ;

then C is a CDm in f¸;±¡¸+1g-cycle.

Th e o r e m A is s h o wn in [1 0 ] t o b e b e s t p o s s ib le . Ob s e r vin g t h a t b e in g a CD¸-c yc le im -
p lie s c · ¸ ¡ 1 ( b y t h e d e ¯ n it io n ) , Th e o r e m A im p lie s t h e fo llo win g r e s u lt .

Cor ollar y A: L et G be a ¸-connected ( ¸ ¸ 1 ) graph and C a longest cycle in G. If

± ¸ n + 2
¸ + 1

+ ¸ ¡ 2 ;

then c · m in f¸ ¡ 1 ; ± ¡ ¸g.

Th u s , t h e m in im u m d e g r e e c-ve r s io n o f B o n d y's c o n je c t u r e is t r u e wit h s o m e s t r e n g t h -
e n in g . Th e t r a n s it io n fr o m m in im u m d e g r e e c-ve r s io n o f B o n d y's c o n je c t u r e t o d e g r e e s u m



Zh. Nikoghosyan 2 1

p-ve r s io n ( t h a t is t h e s o lu t io n o f B o n d y's c o n je c t u r e ) n o w c a n b e c o n s id e r e d a s a t e c h n ic a l
p r o b le m .

S in c e Th e o r e m A a n d Co r o lla r y A a r e e qu iva le n t , we c a n s t a t e t h a t Co r o lla r y A is s h a r p
a s we ll.

In t h is p a p e r we p r e s e n t t wo a n a lo g o u s s h a r p r e s u lt s wit h o u t c o n n e c t ivit y c o n d it io n s
c o n c e r n in g b o t h p a n d c-ve r s io n s .

T heor em 1: L et G be a graph and C a longest cycle in G. If

± ¸ n + 2
¸ + 1

+ ¸ ¡ 2 ;

for some positive integer ¸, then either p · m in f¸ ¡ 2 ; ± ¡ ¸ ¡ 1 g or p ¸ m a xf¸; ± ¡ ¸ + 1 g.

T heor em 2: L et G be a graph and C a longest cycle in G. If

± ¸ n + 2
¸ + 1

+ ¸ ¡ 2 ;

for some positive integer ¸, then either c · m in f¸ ¡ 1 ; ± ¡ ¸g or c ¸ m a xf¸ + 1 ; ± ¡ ¸ + 2 g.

W e s h a ll s h o w 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 . P u t G1 = ( ¸ + 2 ) K¸¡1 + K¸+1.
S in c e ± = 2 ¸ ¡ 1 , p = ¸ ¡ 2 = ± ¡ ¸ ¡ 1 a n d c = ¸ ¡ 1 = ± ¡ ¸, t h e g r a p h G1 s h o ws t h a t
t h e b o u n d s ¸ ¡ 2 a n d ± ¡ ¸ ¡ 1 in Th e o r e m 1 , a n d t h e b o u n d s ¸ ¡ 1 , ± ¡ ¸ in Th e o r e m
2 , a r e s h a r p . N o w p u t G2 = ¸K¸+1 + K¸¡1. S in c e ± = 2 ¸ ¡ 1 , p = ¸ = ± ¡ ¸ + 1 a n d
c = ¸ + 1 = ± ¡ ¸ + 2 , t h e n t h e g r a p h G2 s h o ws t h a t t h e b o u n d s ¸ a n d ± ¡ ¸ + 1 in
Th e o r e m 1 , a n d t h e b o u n d s ¸ + 1 , ± ¡ ¸ + 2 in Th e o r e m 2 a r e s h a r p a s we ll. Fin a lly, le t
G3 = ( ± ¡ ¸ + 2 ) K¸ + K±¡¸+1. Th e n ± = ( n + 1 ) = ( ¸ + 1 ) + ¸ ¡ 2 , p = ¸ ¡ 1 a n d c = ¸,
im p lyin g t h a t t h e b o u n d ( n + 2 ) =( ¸ + 1 ) + ¸ ¡ 2 in Th e o r e m s 1 a n d 2 c a n n o t b e r e la xe d .

In vie w o f Co r o lla r y A a n d Th e o r e m s 1 -2 , Co n je c t u r e s A a n d B c a n b e c o n s id e r a b ly
s t r e n g t h e n e d . Mo r e o ve r , t h e y c a n b e n a t u r a lly e xt e n d e d o n a c c o u n t o f t h e c-ve r s io n .

Conjectur e 1: L et G be a ¸-connected ( ¸ ¸ 1 ) graph and C a longest cycle in G. If

1

¸ + 1
¾¸+1 ¸

n + 2

¸ + 1
+ ¸ ¡ 2 ;

then

p · m in
n
¸ ¡ 2 ; 1

¸ + 1
¾¸+1 ¡ ¸ ¡ 1

o
; c · m in

n
¸ ¡ 1 ; 1

¸ + 1
¾¸+1 ¡ ¸

o
:

Conjectur e 2: L et G be a ¸-connected ( ¸ ¸ 1 ) graph and C a longest cycle in G. If

± ¸ n + 2
¸ + 1

+ ¸ ¡ 2 ;

then p · m in f¸ ¡ 2 ; ± ¡ ¸ ¡ 1 g.

N o w we t u r n t o t h e lo n g c yc le ve r s io n s o f Co r o lla r y A a n d Th e o r e m s 1 -2 .



2 2 On Some Versions of Conjectures of Bondy and Jung

In 2 0 0 1 , Ju n g [2 ] c o n je c t u r e d a c o m m o n g e n e r a liz a t io n o f t wo fu n d a m e n t a l t h e o r e m s in
h a m ilt o n ia n g r a p h t h e o r y d u e t o D ir a c [3 ] ( 1 9 5 2 , ¸ = 2 ) a n d Ju n g [8 ] ( 1 9 7 8 , ¸ = 3 ) .

Conjectur e C: [2 ] L et G be a ¸-connected ( ¸ ¸ 1 ) graph and C a longest cycle in G. If
p ¸ ¸ ¡ 2 , then jCj ¸ (̧ ± ¡ ¸ + 2 ) .

Th e d e g r e e s u m ve r s io n o f Co n je c t u r e C c o n t a in in g t h e t h e o r e m s o f B o n d y [6 ] ( 1 9 7 1 ,
¸ = 2 ) , B e r m o n d [1 4 ] ( 1 9 7 6 , ¸ = 2 ) , L in ia l [1 5 ] ( 1 9 7 6 , ¸ = 2 ) , Fr a is s e a n d Ju n g [7 ] ( 1 9 8 9 ,
¸ = 3 ) a s s p e c ia l c a s e s c a n b e fo r m u la t e d a s fo llo ws .

Conjectur e 3: L et G be a ¸-connected ( ¸ ¸ 1 ) graph and C a longest cycle in G. If
p ¸ ¸ ¡ 2 , then

jCj ¸ ¸
³ 1
¸
¾¸ ¡ ¸ + 2

´
:

In 2 0 0 9 , t h e a u t h o r p r o ve d [1 0 ] t h e fo llo win g .

T heor em B : [1 0 ]. L et G be a ( ¸ + 1 ) -connected ( ¸ ¸ 0 ) graph and C a longest cycle in G.
Then either jCj ¸ ( ¸ + 1 ) ( ± ¡ ¸ + 1 ) or C is a CDm in f¸;±¡¸g-cycle.

Th e o r e m B is s h o wn in [1 0 ] t o b e b e s t p o s s ib le a n d c le a r ly is e qu iva le n t t o t h e fo llo win g .

T heor em C: [1 0 ]. L et G be a ¸-connected ( ¸ ¸ 1 ) graph and C a longest cycle in G. Then
either jCj ¸ ¸ ( ± ¡ ¸ + 2 ) or C is a CDm in f¸¡1;±¡¸+1g-cycle.

U s in g t h e d e ¯ n it io n o f CD¸-c yc le s , we g e t t h e fo llo win g r e s u lt .

Cor ollar y B : L et G be a ¸-connected ( ¸ ¸ 1 ) graph and C a longest cycle in G. If
c ¸ m in f¸ ¡ 1 ; ± ¡ ¸ + 1 g then jCj ¸ (̧ ± ¡ ¸ + 2 ) .

Th u s , c-ve r s io n o f Ju n g 's c o n je c t u r e is t r u e wit h s o m e s t r e n g t h e n in g . Th e t r a n s it io n fr o m
m in im u m d e g r e e c-ve r s io n o f Ju n g 's c o n je c t u r e t o d e g r e e s u m p-ve r s io n ( t h a t is t h e s o lu t io n
o f Ju n g 's c o n je c t u r e ) is a t e c h n ic a l p r o b le m .

In t h is p a p e r we p r e s e n t t wo a n a lo g o u s s h a r p r e s u lt s wit h o u t c o n n e c t ivit y c o n d it io n s .

T heor em 3: L et G be a graph and C a longest cycle in G. If

m in f¸ ¡ 2 ; ± ¡ ¸g · p · m a xf¸ ¡ 2 ; ± ¡ ¸g;

for some positive integer ¸, then jCj ¸ (̧ ± ¡ ¸ + 2 ) .

T heor em 4: L et G be a graph and C a longest cycle in G. If

m in f¸ ¡ 1 ; ± ¡ ¸ + 1 g · c · m a xf¸ ¡ 1 ; ± ¡ ¸ + 1 g;

for some positive integer ¸, then jCj ¸ (̧ ± ¡ ¸ + 2 ) .



Zh. Nikoghosyan 2 3

To s h o w t h a t t h e c o n d it io n s in Th e o r e m s 3 a n d 4 c a n n o t b e r e la xe d , a s s u m e ¯ r s t t h a t
m in f¸ ¡ 2 ; ± ¡ ¸g = ¸ ¡ 2 , t h a t is ¸ ¡ 2 · ± ¡ ¸. P u t H1 = ( ± ¡ ¸ + 4 ) K¸¡2 + K±¡¸+3.
Cle a r ly p = ¸ ¡ 3 , c = ¸ ¡ 2 a n d jCj = ( ¸ ¡ 1 ) ( ± ¡ ¸ + 3 ) . R e c a llin g t h a t ¸ ¡ 2 · ± ¡ ¸, we
g e t

( ¸ ¡ 1 ) ( ± ¡ ¸ + 3 ) = (̧ ± ¡ ¸ + 2 ) + ( 2 ¸ ¡ ± ¡ 2 ) ¡ 1 < (̧ ± ¡ ¸ + 2 ) ;
im p lyin g t h a t t h e b o u n d s ¸ ¡ 2 a n d ¸ ¡ 1 in Th e o r e m s 3 a n d 4 c a n n o t b e r e la xe d . N o w
a s s u m e t h a t m in f¸ ¡ 2 ; ± ¡ ¸g = ± ¡ ¸, t h a t is ¸ ¡ 2 ¸ ± ¡ ¸. P u t H2 = ( ¸ + 2 ) K±¡¸ + K¸+1.
Cle a r ly p = ± ¡ ¸ ¡ 1 , c = ± ¡ ¸ a n d jCj = ( ¸ + 1 ) ( ± ¡ ¸ + 1 ) . S in c e ¸ ¡ 2 ¸ ± ¡ ¸, we h a ve
( ¸ + 1 ) ( ± ¡ ¸ + 1 ) < (̧ ± ¡ ¸ + 2 ) , im p lyin g t h a t t h e b o u n d s ± ¡ ¸ a n d ± ¡ ¸ + 1 in Th e o r e m s
3 a n d 4 c a n n o t b e r e la xe d a s we ll.

In vie w o f Co r o lla r y B a n d Th e o r e m s 3 -4 , Co n je c t u r e C a n d Co n je c t u r e 3 c a n b e c o n s id -
e r a b ly s t r e n g t h e n e d . Mo r e o ve r , t h e y c a n b e n a t u r a lly e xt e n d e d o n a c c o u n t o f t h e c-ve r s io n .

Conjectur e 4: L et G be a ¸-connected ( ¸ ¸ 1 ) graph and C a longest cycle in G. If either

p ¸ m in
n
¸ ¡ 2 ; 1

¸
¾¸ ¡ ¸

o
or c ¸ m in

n
¸ ¡ 1 ; 1

¸
¾¸ ¡ ¸ + 1

o
;

then

jCj ¸ ¸
³ 1
¸
¾¸ ¡ ¸ + 2

´
:

Conjectur e 5: L et G be a ¸-connected ( ¸ ¸ 1 ) graph and C a longest cycle in G. If
p ¸ m in f¸ ¡ 2 ; ± ¡ ¸g, then jCj ¸ (̧ ± ¡ ¸ + 2 ) .

To p r o ve Th e o r e m s 1 -4 , we n e e d t h e fo llo win g t wo t h e o r e m s [1 1 ] b y t h e a u t h o r .

T heor em D: [1 1 ] ( 2 0 1 3 ) . L et G be a graph and C a longest cycle in G. Then jCj ¸
( p + 2 ) ( ± ¡ p ) .

T heor em E : [1 1 ] ( 2 0 1 3 ) . L et G be a graph and C a longest cycle in G. Then jCj ¸
( c + 1 ) ( ± ¡ c + 1 ) .

2 . P r o o fs

P r oof of T heor em 1. B y t h e h yp o t h e s is , n · ( ¸ + 1 ) ( ± ¡ ¸ + 2 ) ¡ 2 . On t h e o t h e r h a n d ,
we h a ve n ¸ jCj + p + 1 . S in c e jCj ¸ ( p + 2 ) ( ± ¡ p ) ( b y Th e o r e m D ) , we h a ve

n ¸ ( p + 2 ) ( ± ¡ p) + p + 1 = ( p + 2 ) ( ± ¡ p + 1 ) ¡ 1 :

Th u s
( ¸ + 1 ) ( ± ¡ ¸ + 2 ) ¸ ( p + 2 ) ( ± ¡ p + 1 ) + 1 ;

wh ic h is e qu iva le n t t o
( ¸ ¡ p ¡ 1 ) ( ± ¡ ¸ ¡ p ) ¸ 1 :

Th e n we h a ve e it h e r
¸ ¡ p ¡ 1 ¸ 1 a n d ± ¡ ¸ ¡ p ¸ 1 ;



2 4 On Some Versions of Conjectures of Bondy and Jung

wh ic h is e qu iva le n t t o p · m in f¸ ¡ 2 ; ± ¡ ¸ ¡ 1 g, o r
¸ ¡ p ¡ 1 · ¡ 1 a n d ± ¡ ¸ ¡ p · ¡ 1 ;

wh ic h is e qu iva le n t t o p ¸ m a xf¸; ± ¡ ¸ + 1 g.

P r oof of T heor em 2. B y t h e h yp o t h e s is , n · ( ¸ + 1 ) ( ± ¡ ¸ + 2 ) ¡ 2 . On t h e o t h e r h a n d ,
we h a ve n ¸ jCj + c. S in c e jCj ¸ ( c + 1 ) ( ± ¡ c + 1 ) ( b y Th e o r e m E ) , we h a ve

n ¸ ( c + 1 ) ( ± ¡ c + 1 ) + c = ( c + 1 ) ( ± ¡ c + 2 ) ¡ 1 ;
im p lyin g t h a t

( ¸ + 1 ) ( ± ¡ ¸ + 2 ) ¸ ( c + 1 ) ( ± ¡ c + 2 ) + 1 ;
Th is is e qu iva le n t t o

( ¸ ¡ c) ( ± ¡ ¸ ¡ c + 1 ) ¸ 1 :
Th e n we h a ve e it h e r

¸ ¡ c ¸ 1 a n d ± ¡ ¸ ¡ c + 1 ¸ 1 ;
wh ic h is e qu iva le n t t o c · m in f¸ ¡ 1 ; ± ¡ ¸g, o r

¸ ¡ c · ¡ 1 a n d ± ¡ ¸ ¡ c + 1 · ¡ 1 ;
wh ic h is e qu iva le n t t o c ¸ m a xf¸ + 1 ; ± ¡ ¸ + 2 g.

P r oof of T heor em 3. W e d is t in g u is h t wo c a s e s .
Case 1. m in f¸ ¡ 2 ; ± ¡ ¸g = ¸ ¡ 2 .

B y t h e h yp o t h e s is , ¸ ¡ 2 · p · ± ¡ ¸. Th e n
( p ¡ ¸ + 2 ) ( ± ¡ p ¡ )̧ ¸ 0 ;

wh ic h is e qu iva le n t t o
( p + 2 ) ( ± ¡ p) ¸ (̧ ± ¡ ¸ + 2 ) :

S in c e jCj ¸ ( p + 2 ) ( ± ¡ p) ( b y Th e o r e m D ) , we h a ve jCj ¸ ¸ ( ± ¡ ¸ + 2 ) .
Case 2. m in f¸ ¡ 2 ; ± ¡ ¸g = ± ¡ ¸.

B y t h e h yp o t h e s is , ± ¡ ¸ · p · ¸ ¡ 2 , im p lyin g t h a t
( p ¡ ¸ + 2 ) ( ± ¡ p ¡ )̧ ¸ 0

a n d we c a n a r g u e a s in Ca s e 1 .

P r oof of T heor em 4. W e d is t in g u is h t wo c a s e s .
Case 1. m in f¸ ¡ 1 ; ± ¡ ¸ + 1 g = ¸ ¡ 1 .

B y t h e h yp o t h e s is , ¸ ¡ 1 · c · ± ¡ ¸ + 1 . Th e n
( c ¡ ¸ + 1 ) ( ± ¡ c ¡ ¸ + 1 ) ¸ 0 ;

wh ic h is e qu iva le n t t o
( c + 1 ) ( ± ¡ c + 1 ) ¸ ¸ ( ± ¡ ¸ + 2 ) :

S in c e jCj ¸ ( c + 1 ) ( ± ¡ c + 1 ) ( b y Th e o r e m E ) , we h a ve jCj ¸ (̧ ± ¡ ¸ + 2 ) .
Case 2. m in f¸ ¡ 1 ; ± ¡ ¸ + 1 g = ± ¡ ¸ + 1 .

B y t h e h yp o t h e s is , ± ¡ ¸ + 1 · c · ¸ ¡ 1 , im p lyin g t h a t
( c ¡ ¸ + 1 ) ( ± ¡ c ¡ ¸ + 1 ) ¸ 0

a n d we c a n a r g u e a s in Ca s e 1 .



Zh. Nikoghosyan 2 5

Refer ences

[1 ] J. A . B o n d y, \ L o n g e s t p a t h s a n d c yc le s in g r a p h s o f h ig h d e g r e e " , R esearch R eport
COR R 80-16. University of W aterloo, W a t e r lo o , On t a r io , 1 9 8 0 .

[2 ] H . A . Ju n g , \ D e g r e e b o u n d s fo r lo n g p a t h s a n d c yc le s in k-c o n n e c t e d g r a p h s " ,in Com-
putational D iscrete M athematics, L e c t u r e N o t e s in Co m p u t e r S c ie n c e , S p r in g e r , B e r lin ,
vo l. 2 1 2 2 , p p . 5 6 -6 0 , 2 0 0 1 .

[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 roceedings of the L ondon M athe-
matical Society, vo l. 2 , p p . 6 9 -8 1 , 1 9 5 2 .

[4 ] O. Or e , \ A n o t e o n h a m ilt o n ia n c ir c u it s " , American M athematical M onthly, vo l. 6 7 , p .
5 5 , 1 9 6 0 .

[5 ] C. S t . J. A . N a s h -W illia m s , \ E d g e -d is jo in t h a m ilt o n ia n c yc le s in g r a p h s wit h ve r t ic e s
o f la r g e va le n c y" , in: L . M irsky, ed., "Studies in P ure M athematics", A c a d e m ic P r e s s ,
S a n D ie g o / L o n d o n , p p . 1 5 7 -1 8 3 , 1 9 7 1 .

[6 ] 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 athematics, vo l. 1 , n o . 2 , p p . 1 2 1 -1 3 1 ,
1 9 7 1 .

[7 ] P . Fr a is s e a n d H . A . Ju n g , \ L o n g e s t c yc le s a n d in d e p e n d e n t s e t s in k-c o n n e c t e d g r a p h s " ,
in V.R . K ulli. ed., R ecent Studies in Graph Theory, ( V is c h wa In t e r n a t io n a l P u b lis h in g
Gu lb a r g a , In d ia , p p . 1 1 4 -1 3 9 , 1 9 8 9 .

[8 ] H . A . Ju n g , \ On m a xim a l c ir c u it s in ¯ n it e g r a p h s " , Annals of D iscrete M athematics,
vo l. 3 , p p . 1 2 9 -1 4 4 , 1 9 7 8 .

[9 ] H . A . Ju n g , \ L o n g e s t c ir c u it s in 3 -c o n n e c t e d g r a p h s " , Colloquium M athematical Society
J anos B olyai 37, F inite and In¯nite sets, E ger, p p . 4 0 3 -4 3 8 , 1 9 8 1 .

[1 0 ] Zh . G. N iko g h o s ya n , \ D ir a c -t yp e g e n e r a liz a t io n s c o n c e r n in g la r g e c yc le s in g r a p h s " ,
D iscrete M athematics, vo l. 3 0 9 , n o . 8 , p p . 1 9 2 5 -1 9 3 0 , 2 0 0 9 .

[1 1 ] Zh . G. N iko g h o s ya n , \ A d va n c e d L o we r B o u n d s fo r t h e Cir c u m fe r e n c e " , Graphs and
Combinatorics, vo l. 2 9 , n o . 5 , p p . 1 5 3 1 -1 5 4 1 , 2 0 1 3 .

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

[1 3 ] Y . Zo u , \ A g e n e r a liz a t io n o f a t h e o r e m o f Ju n g " , J . Nanjing Normal University Natural
Science E dition, vo l. 2 , p p . 8 -1 1 , 1 9 8 7 .

[1 4 ] J. C. B e r m o n d , \ On h a m ilt o n ia n wa lks " , Congressus Numerantium, vo l. 1 5 , p p . 4 1 -5 1 ,
1 9 7 6 .

[1 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 athematics, vo l.
1 5 , n o . 3 , p p . 2 9 7 -3 0 0 , 1 9 7 6 .

Submitted 12.10.2015, accepted 20.01.2016

´áݹÇÇ ¨ ÚáõÝ·Ç í³ñϳÍÝ»ñÇ áñáß ï³ñµ»ñ³ÏÝ»ñÇ Ù³ëÇÝ

Ä. ÜÇÏáÕáëÛ³Ý

²Ù÷á÷áõÙ

¸Çóáõù C-Ý G ·ñ³ýÇ ³Ù»Ý³»ñϳñ óÇÏÉÝ ¿, ·-Ý` ϳå³Ïóí³ÍáõÃÛ³Ý µÝáõó·ñÇãÁ,
ÇëÏ p-Ý` G-C-Ç ³Ù»Ý³»ñϳñ ßÕóÛÇ »ñϳñáõÃÛáõÝÁ: гÙÇÉïáÝÛ³Ý ·ñ³ýÝ»ñÇ
ï»ëáõÃÛ³Ý ³é³í»É ѳÛïÝÇ ÑÇÙݳñ³ñ ³ñ¹ÛáõÝùÝ»ñÁ` ëï³óí³Í ¸Çñ³ÏÇ, úñ»Ç,



2 6 On Some Versions of Conjectures of Bondy and Jung

Ü»ß-ìÇÉÛ³ÙëÇ, ´áݹÇÇ, ÚáõÝ·Ç ¨ ³ÛÉáó ÏáÕÙÇó, Çñ»ÝóÇó Ý»ñϳ۳óÝáõÙ »Ý C óÇÏÉÇ
»ñϳñáõÃÛ³Ý ·Ý³Ñ³ï³Ï³ÝÝ»ñ` ³ñï³Ñ³Ûïí³Í ·ñ³ýÇ ·³·³ÃÝ»ñÇ Ýí³½³·áõÛÝ
³ëïÇ׳Ýáí ϳ٠³ëïÇ׳ݳÛÇÝ ·áõÙ³ñÝ»ñáí ¨ ·, p µÝáõó·ñÇãÝ»ñÇ Ù³ëݳíáñ
³ñÅ»ùÝ»ñáí, »ñµ · · 3 ¨ p · 1 (p = ¡1 ¹»åùÁ ѳٳñÅ»ù ¿ V ( G ¡ C ) = ;
å³ÛÙ³ÝÇÝ, ¨ C-Ý ÏáãíáõÙ ¿ ѳÙÇÉïáÝÛ³Ý óÇÏÉ; ÇëÏ p = 0 ¹»åùáõÙ V ( G¡C ) -Ý ·³·³ÃÝ»ñÇ
³ÝÏ³Ë µ³½ÙáõÃÛáõÝ ¿, ¨ C-Ý ÏáãíáõÙ ¿ ¹áÙÇݳÝï óÇÏÉ): ´áݹÇÇ (1980) ¨ ÚáõÝ·Ç (2001)
ÁݹѳÝñ³óí³Í í³ñϳÍÝ»ñÁ ÑÇÙÝíáõÙ »Ý ³ëïÇ׳ݳÛÇÝ ·áõÙ³ñÝ»ñÇ íñ³, áñï»Õ p -Ý
¨ ·-Ý Ñ³Ý¹»ë »Ý ·³ÉÇë áñå»ë ÁݹѳÝñ³Ï³Ý å³ñ³Ù»ïñ»ñ` Áݹ·ñÏ»Éáí í»ñáÑÇßÛ³É
³ñ¹ÛáõÝùÝ»ñÁ áñå»ë Ù³ëݳíáñ ¹»åù»ñ: ²Ûë í³ñϳÍÝ»ñÁ ÁݹѳÝáõñ ¹»åùáõÙ ÙÝáõÙ
»Ý ãÉáõÍí³Í: 2009-ÇÝ Ñ»ÕÇݳÏÇ ÏáÕÙÇó ÉáõÍí»É »Ý ´áݹÇÇ ¨ ÚáõÝ·Ç í³ñϳÍÝ»ñÇ
Ýí³½³·áõÛÝ ³ëïÇ׳ݳÛÇÝ c¡ ï³ñµ»ñ³ÏÝ»ñÁ, áñï»Õ c- Ý Ý»ñϳ۳óÝáõÙ ¿ V ( G ¡ C ) -Ç
³Ù»Ý³»ñϳñ óÇÏÉÇ »ñϳñáõÃÛáõÝÁ (Discrete Math, v.309, 2009, 1925-1930): ÐÇÙÝí»Éáí
Ñ»ÕÇݳÏÇ Ù»Ï ³ÛÉ ³ß˳ï³ÝùÇ íñ³ (Graphs and Combinatorics, v.29, 2013, 1531-
1541), Ý»ñϳ ³ß˳ï³ÝùáõÙ ³å³óáõóíáõÙ »Ý ÙÇ ù³ÝÇ Ñ³Ù³ÝÙ³Ý ³ñ¹ÛáõÝùÝ»ñ`
Áݹ·ñÏ»Éáí ´áݹÇÇ ¨ ÚáõÝ·Ç Ýí³½³·áõÛÝ ³ëïÇ׳ݳÛÇÝ p ¨ c ï³ñµ»ñ³ÏÝ»ñÁ ³é³Ýó
ϳå³Ïóí³ÍáõÃÛ³Ý å³ÛÙ³ÝÇ, áñáÝù Çñ»Ýó Ñ»ñÃÇÝ ÍÝáõÙ »Ý ³Ûë í³ñϳÍÝ»ñÇ ÙÇ
ù³ÝÇ Ýáñ áõŻճóí³Í ¨ ÁݹɳÛÝí³Í ï³ñµ»ñ³ÏÝ»ñ: êï³óí³Í µáÉáñ ³ñ¹ÛáõÝùÝ»ñÁ
ɳí³óÝ»ÉÇ ã»Ý:

Î íåêîòîðûõ âåðñèÿõ ãèïîòåç Áîíäè è Þíãà
Æ. Íèêîãîñÿí

Àííîòàöèÿ

Íàèáîëåå èçâåñòíûå ôóíäàìåíòàëüíûå òåîðåìû â òåîðèè ãàìèëüòîíîâîñòè
ãðàôîâ (àâòîðû: Äèðàê, Îðå, Íåø-Âèëüÿìñ, Áîíäè, Þíã è ò.ä.) ïðåäñòàâëÿþò
ðàçëè÷íûå îöåíêè äëèíû äëèííåéøåãî öèêëà C ãðàôà G â òåðìèíàõ
ìèíèìàëüíîé ñòåïåíè âåðøèí èëè ñóìì ñòåïåíåé, ñâÿçíîñòè · è äëèíû p
äëèííåéøåé öåïè â G ¡ C äëÿ ÷àñòíûõ ñëó÷àåâ êîãäà · · 3 è p · 1 (â ñëó÷àå
p = ¡ 1 èìååò ìåñòî V ( G ¡ C ) = è C íàçûâàåòñÿ ãàìèëüòîíîâûì öèêëîì; åñëè
p = 0 òî V ( G ¡ C ) ÿâëÿåòñÿ íåçàâèñèìûì ìíîæåñòâîì âåðøèí è C íàçûâàåòñÿ
äîìèíàíòíûì öèêëîì). Îáîáùåííûå ãèïîòåçû Áîíäè (1980) è Þíãà (2001)
îñíîâàíû íà ñóììàõ ñòåïåíåé, ãäå p è · ÿâëÿþòñÿ ïàðàìåòðàìè, âêëþ÷àþùèå
âûøåóïàìÿíóòûå ðåçóëüòàòû êàê ÷àñòíûå ñëó÷àè. Ýòè ãèïîòåçû îñòàþòñÿ
íåðåøåííûìè. Â 2009 ã àâòîð ðåøèë c-âåðñèè ãèïîòåç Áîíäè è Þíãà íà îñíîâå
ìèíèìàëüíîé ñòåïåíè, ãäå c îáîçíà÷àåò äëèíó äëèííåéøåãî öèêëà â V ( G¡C ) (Dis-
crete Math, v.309, 2009, 1925-1930). Íà îñíîâå äðóãîãî ðåçóëüòàòà àâòîðà (Graphs
and Combinatorics, v.29, 2013, 1531-1541), â ðàáîòå äîêàçûâàåòñÿ ñïðàâåäëèâîñòü
íåêåòîðûõ âåðñèé ãèïîòåç Áîíäè è Þíãà, âêëþ÷àþùèå p è c-âåðñèè áåç óñëîâèÿ
ñâÿçíîñòè, êîòîðûå â ñâîþ î÷åðåäü ïîðîæäàþò íîâûå óñèëåííûå è ðàñøèðåííûå
âåðñèè ýòèõ ãèïîòåç. Âñå ïîëó÷åííûå ðåçóëüòàòû íåóëó÷øàåìû.