Mathematical Problems of Computer Science 59, 7–15, 2023.

doi:10.51408/1963-0097

UDC 519.1

A Note on Large Cycles in Graphs

Around Conjectures of Bondy and Jung

Zhora G. Nikoghosyan

Institute for Informatics and Automation Problems of NAS RA, Yerevan, Armenia

e-mail: zhora@iiap.sci.am

Abstract

New sufficient conditions are derived for generalized cycles (including Hamilton and
dominating cycles as special cases) in an arbitrary k-connected (k = 1, 2, ...) graph,
which prove the truth of Bondy’s (1980) famous conjecture for some variants signif-
icantly improving the result expected by the given hypothesis. Similarly, new lower
bounds for the circumference (the length of a longest cycle) are established for the
reverse hypothesis proposed by Jung (2001) combined inspiring new improved versions
of the original conjectures of Bondy and Jung.
Keywords: Hamilton cycle, Dominating cycle, Longest cycle, Large cycle.
Article info: Received 27 January 2021; sent for review 14 February 2022; received
in revised form 11 January 2023; accepted 7 March 2023.

1. Introduction

We consider only finite undirected graphs without loops or multiple edges. The set of vertices
of a graph G is denoted by V (G); the set of edges by E(G). For a subset S of V (G), we
denote by G−S the maximum subgraph of G with the vertex set V (G)−S. For a subgraph
H of G, we use G − H, short for G − V (H). A good reference for any undefined terms is [3].

Let α and δ be the independence number and the minimum degree of a graph G, respec-
tively. We define σk by the minimum degree sum of any k independent vertices if α ≥ k; if
α < k, we set σk = +∞. In particular, we have σ1 = δ.

A simple cycle (or just a cycle) Q of order t (the number of vertices) is a sequence
v1v2...vtv1 of distinct vertices v1, ..., vt with vivi+1 ∈ E(G) for each i ∈ {1, ..., t}, where
vt+1 = v1. When t = 1, the cycle v1 coincides with the vertex v1. So, by this standard
definition, all vertices and edges in a graph can be considered as cycles of orders 1 and 2,
respectively. Such an extension of the cycle definition allows to avoid unnecessary repetition
”let G be a graph of order n ≥ 3” in a large number of results. Further, a simple path (or
just a path) of order t is a sequence v1v2...vt of distinct vertices v1, ..., vt with vivi+1 ∈ E(G)
for each i ∈ {1, ..., t − 1}.

A graph G is Hamiltonian if G contains a Hamilton cycle, i.e., a cycle of order |V (G)|.

7



8 A Note on Large Cycles in Graphs Around Conjectures of Bondy and Jung

Now let Q be an arbitrary cycle in G. We say that Q is a dominating cycle in G if
V (G − Q) is an independent set of vertices.

The first type of generalized cycles, including Hamilton and dominating cycles as special
cases, was introduced by Bondy [4]. For a positive integer λ, Q is said to be a Dλ-cycle if
|H| ≤ λ − 1 for every component H of G − Q. Alternatively, Q is a Dλ-cycle of G if and
only if every connected subgraph of order λ of G has at least one vertex with Q in common.
Thus, a Dλ-cycle dominates all connected subgraphs of order λ. By this definition, Q is a
Hamilton cycle if and only if Q is a D1-cycle. Analogously, Q is a dominating cycle if and
only if Q is a D2-cycle.

We now present another two types of more interesting generalized cycles that form the
main topic of this paper. For a positive integer λ, the cycle Q is called a PDλ-cycle (PD
- Path Dominating) if each path of order at least λ in G has at least one vertex with Q in
common. Similarly, we call the cycle Q a CDλ-cycle (CD - Cycle Dominating; introduced
in [13]) if each cycle of order at least λ has at least one vertex with Q in common. In fact,
a PDλ-cycle dominates all paths of order λ in G; and a CDλ-cycle dominates all cycles of
order λ in G. In terms of PDλ and CDλ-cycles, Q is a Hamilton cycle if and only if either
Q is a PD1-cycle or a CD1-cycle. Further, Q is a dominating cycle if and only if either Q is
a PD2-cycle or a CD2-cycle.

Throughout the paper, we consider a graph G on n vertices with minimum degree δ and
connectivity κ. Further, let C be a longest cycle in G with c = |C|, and let p and c denote
the orders of a longest path and a longest cycle in G − C, respectively. In particular, C is a
Hamilton cycle if and only if p ≤ 0 or c ≤ 0. Similarly, C is a dominating cycle if and only
if p ≤ 1 or c ≤ 1.

In 1980, Bondy [4] conjectured a common generalization of some well-known degree-sum
conditions for PDλ-cycles (called (σ, p)-version) including Hamilton cycles (PD1-cycles) and
dominating cycles (PD2-cycles) as special cases.

Conjecture 1. (Bondy [4],1980): (σ, p)-version
Let C be a longest cycle in a λ-connected (1 ≤ λ ≤ δ) graph G of order n. If σλ+1 ≥
n + λ(λ − 1), then p ≤ λ − 1.

Parts of Conjecture 1 were proved for λ = 1, 2, 3.

(a) κ ≥ 1, σ2 ≥ n =⇒ p ≤ 0 (Ore[15], 1960),
(b) κ ≥ 2, σ3 ≥ n + 2 =⇒ p ≤ 1 (Bondy[4], 1980),
(c) κ ≥ 3, σ4 ≥ n + 6 =⇒ p ≤ 2 (Zou[17], 1987).

For the general case, Conjecture 1 is still open.
The long cycles analogue (the so called reverse version) of Bondy’s conjecture (Conjecture

1) can be formulated as follows.

Conjecture 2. (reverse, σ, p)-version
Let C be a longest cycle in a λ-connected (1 ≤ λ ≤ δ) graph G. If p ≥ λ − 1, then
c ≥ σλ − λ(λ − 2).

Parts of Conjecture 2 were proved for λ = 1, 2, 3, 4.

(d) κ ≥ 1, p ≥ 0 =⇒ c ≥ σ1 + 1 (Dirac[6], 1952),



Zh. Nikoghosyan 9

(e) κ ≥ 2, p ≥ 1 =⇒ c ≥ σ2 (Bondy[2], 1971; Bermond[1], 1976; Linial[11], 1976),
(f) κ ≥ 3, p ≥ 2 =⇒ c ≥ σ3 − 3 (Fraisse, Jung[8], 1989),
(g) κ ≥ 4, p ≥ 3 =⇒ c ≥ σ4 − 8 (Chiba, Tsugaki, Y amashita[5], 2014).

Note that the initial motivations of Conjecture 1 and Conjecture 2 come from their
minimal degree versions - the most popular and much studied versions, which also remain
unsolved.

Conjecture 3. (Bondy [4],1980): (δ, p)-version
Let C be a longest cycle in a λ-connected (1 ≤ λ ≤ δ) graph G of order n. If δ ≥ n+2

λ+1
+λ−2,

then p ≤ λ − 1.

Conjecture 4. (Jung [10], 2001): (reverse, δ, p)-version
Let C be a longest cycle in a λ-connected (1 ≤ λ ≤ δ) graph G. If p ≥ λ − 1, then
c ≥ λ(δ − λ + 2).

Parts of Conjecture 3 were proved for λ = 1, 2, 3.

(h) κ ≥ 1, δ ≥ n
2

=⇒ p ≤ 0 (Dirac[6], 1952),
(i) κ ≥ 2, δ ≥ n+2

3
=⇒ p ≤ 1 (Nash − Williams[12], 1971),

(j) κ ≥ 3, δ ≥ n+6
4

=⇒ p ≤ 2 (Fan[7], 1987).

Parts of Conjecture 4 were proved for λ = 1, 2, 3, 4.

(k) κ ≥ 1, p ≥ 0 =⇒ c ≥ δ + 1 (Dirac[6], 1952),
(l) κ ≥ 2, p ≥ 1 =⇒ c ≥ 2δ (Dirac[6], 1952),
(m) κ ≥ 3, p ≥ 2 =⇒ c ≥ 3δ − 3 (V oss, Zuluaga[16], 1977),
(n) κ ≥ 4, p ≥ 3 =⇒ c ≥ 4δ − 8 (Jung[9], 1990).

Note that CDλ-cycles are more suitable for research than PDλ-cycles since cycles in
G − C are more symmetrical than paths in view of the connections between G − C and
CDλ-cycles. This is the main reason why some minimum degree versions of Conjectures 1
and 2 have been solved just for CDλ-cycles.

According to the above arguments, it is natural to consider the exact analogues of Bondy’s
generalized conjecture (Conjecture 1) and its reverse version (Conjecture 2) for CDλ-cycles,
which we call (σ, c) and (reverse, σ, c)-versions, respectively.

Conjecture 5. (σ, c)-version
Let C be a longest cycle in a λ-connected (1 ≤ λ ≤ δ) graph G of order n. If σλ+1 ≥
n + λ(λ − 1), then c ≤ λ − 1.

Conjecture 6. (reverse, σ, c)-version
Let C be a longest cycle in a λ-connected (1 ≤ λ ≤ δ) graph. If c ≥ λ − 1, then c ≥
σλ − λ(λ − 2).

In 2009, the author proved [14] the validity of minimum degree versions of Conjectures
5 and 6.



10 A Note on Large Cycles in Graphs Around Conjectures of Bondy and Jung

Theorem 1. ([14], 2009): (δ, c)-version
Let C be a longest cycle in a λ-connected (1 ≤ λ ≤ δ graph G of order n. If δ ≥ n+2

λ+1
+ λ − 2,

then c ≤ λ − 1.
Theorem 2. ([14], 2009): (reverse, δ, c)-version
Let C be a longest cycle in a λ-connected (1 ≤ λ ≤ δ) graph. If c ≥ λ−1, then c ≥ λ(δ−λ+2).

Actually, in [14], a significantly stronger result than Theorem 1 was proved showing that
the conclusion c ≤ λ − 1 in Theorem 1 can be strengthened to c ≤ min{λ − 1, δ − λ}, called
c-improvement.

Theorem 3. ([14], 2009): (δ, c)-version, c-improvement
Let C be a longest cycle in a λ-connected (1 ≤ λ ≤ δ) graph G of order n. If δ ≥ n+2

λ+1
+λ−2,

then c ≤ min{λ − 1, δ − λ}.
Analogously, the condition c ≥ λ − 1 in Theorem 2 was weakened [14] to c ≥ min{λ −

1, δ − λ + 1}.
Theorem 4. ([14], 2009): (reverse, δ, c)-version, c-improvement
Let C be a longest cycle in a λ-connected (1 ≤ λ ≤ δ) graph G. If c ≥ min{λ − 1, δ − λ + 1},
then c ≥ λ(δ − λ + 2).

In this paper, we present new analogous further improvements of Theorems 1, 2, 3, 4
inspiring new conjectures in forms of improvements of the initial generalized conjectures of
Bondy and Jung.

2. Results

First, we prove that the connectivity condition κ ≥ λ in Theorem 1 can be weakened to
κ ≥ min{λ, δ − λ + 1}.
Theorem 5. (δ, c)-version, κ-improvement
Let C be a longest cycle in a graph G of order n and λ a positive integer with 1 ≤ λ ≤ δ. If
κ ≥ min{λ, δ − λ + 1} and δ ≥ n+2

λ+1
+ λ − 2, then c ≤ λ − 1.

Analogously, we prove that the connectivity condition κ ≥ λ in Theorem 2 can be
weakened to κ ≥ min{λ, δ − λ + 2}.
Theorem 6. (reverse, δ, c)-version, κ-improvement
Let C be a longest cycle in a graph G and λ a positive integer with 1 ≤ λ ≤ δ. If κ ≥
min{λ, δ − λ + 2} and c ≥ λ − 1, then c ≥ λ(δ − λ + 2).

Next, we prove that the conclusion c ≤ λ − 1 in Theorem 5 can be strengthened to
c ≤ min{λ − 1, δ − λ}.
Theorem 7. (δ, c)-version, (c, κ)-improvement
Let C be a longest cycle in a graph G of order n and λ a positive integer with 1 ≤ λ ≤ δ. If
κ ≥ min{λ, δ − λ + 1} and δ ≥ n+2

λ+1
+ λ − 2, then c ≤ min{λ − 1, δ − λ}.

Finally, we prove that the condition c ≥ λ − 1 in Theorem 6 can be weakened to c ≥
min{λ − 1, δ − λ + 1}.
Theorem 8. (reverse, δ, c)-version, (c, κ)-improvement
Let C be a longest cycle in a graph G and λ a positive integer with 1 ≤ λ ≤ δ. If κ ≥
min{λ, δ − λ + 2} and c ≥ min{λ − 1, δ − λ + 1}, then c ≥ λ(δ − λ + 2).



Zh. Nikoghosyan 11

3. Generalized Improvements of Conjectures of Bondy and Jung

Motivated by Theorems 5, 6, 7, 8 (minimum degree versions) with Conjectures 1 and 2, in this
section we propose their exact analogs in terms of degree sums as generalized improvements
of Bondy and Jung Conjectures.

Conjecture 7. (σ, c)-version, (c, κ)-improvement
Let C be a longest cycle in a graph G of order n and λ a positive integer. If κ ≥ min{λ, δ −
λ + 1} and σλ+1 ≥ n + λ(λ − 1), then c ≤ min{λ − 1, δ − λ}.

Conjecture 8. (reverse, σ, c)-version, (c, κ)-improvement
Let C be a longest cycle in a graph G and λ a positive integer. If κ ≥ min{λ, δ − λ + 2} and
c ≥ min{λ − 1, δ − λ + 1}, then c ≥ σλ − λ(λ − 2).

Conjecture 9. (σ, p)-version, (p, κ)-improvement
Let C be a longest cycle in a graph G of order n and λ a positive integer. If κ ≥ min{λ, δ −
λ + 1} and σλ+1 ≥ n + λ(λ − 1), then p ≤ min{λ − 1, δ − λ}.

Conjecture 10. (reverse, σ, p)-version, (p, κ)-improvement
Let C be a longest cycle in a graph G and λ a positive integer. If κ ≥ min{λ, δ − λ + 2} and
p ≥ min{λ − 1, δ − λ + 1}, then c ≥ σλ − λ(λ − 2).

4. Proofs

Proof of Theorem 7. We shall prove that c ≤ min{λ − 1, δ − λ} under the conditions

κ ≥ min{λ, δ − λ + 1}, δ ≥
n + 2

λ + 1
+ λ − 2

for each 1 ≤ λ ≤ δ. If min{λ, δ − λ + 1} = λ, that is λ ≤ ⌊δ+1
2
⌋, then we shall prove that

c ≤ λ − 1 under the conditions

κ ≥ λ, δ ≥
n + 2

λ + 1
+ λ − 2.

But the latter follows from Theorem 1 for all λ = 1, 2, ..., ⌊δ+1
2
⌋ immediately.

Now let min{λ, δ − λ + 1} = δ − λ + 1, that is λ ≥ ⌊δ+2
2
⌋. To conclude the proof, it

remains to show that

κ ≥ δ − λ + 1, δ ≥
n + 2

λ + 1
+ λ − 2 ⇒ c ≤ δ − λ

(
λ = δ, δ − 1, ...,

⌊
δ + 2

2

⌋)
. (1)

Put δ − λ + 1 = µ. Acording to this notation, (1) is equivalent to

κ ≥ µ, δ ≥
n + 2

δ − µ + 2
+ δ − µ − 1 ⇒ c ≤ µ − 1

(
µ = 1, 2, ...,

⌊
δ + 1

2

⌋)
. (2)

In (2), the inequality

δ ≥
n + 2

δ − µ + 2
+ δ − µ − 1



12 A Note on Large Cycles in Graphs Around Conjectures of Bondy and Jung

is equivalent to

δ ≥
n + 2

µ + 1
+ µ − 2,

implying that (2) is equivalent to

κ ≥ µ, δ ≥
n + 2

µ + 1
+ µ − 2 ⇒ c ≤ µ − 1

(
µ = 1, 2, ...,

⌊
δ + 1

2

⌋)
. (3)

Observing that (3) follows from Theorem 1 immediately, we obtain

(1) ≡ (2) ≡ (3) ⇐ ”Theorem 1”.

Theorem 7 is proved.

Proof of Theorem 5. Let G be a graph with

κ ≥ min{λ, δ − λ + 1}, δ ≥
n + 2

λ + 1
+ λ − 2

for each 1 ≤ λ ≤ δ. We shall prove that c ≤ λ−1. Observing that min{λ−1, δ −λ} ≤ λ−1,
we can weaken the conclusion c ≤ min{λ − 1, δ − λ} in Theorem 7 to c ≤ λ − 1 and the
result follows immediatly.

Proof of Theorem 8. Let G be a graph with

κ ≥ min{λ, δ − λ + 2}, c ≥ min{λ − 1, δ − λ + 1}

for each 1 ≤ λ ≤ δ. We shall prove that c ≥ λ(δ − λ + 2). If λ = 1, then the result follows
from the fact that each graph has a cycle of length at least δ + 1 [6]. Let λ ≥ 2. Further, if
min{λ, δ−λ+2} = λ, then we are done by Theorem 2. Now let min{λ, δ−λ+2} = δ−λ+2,
that is λ ≥ ⌊δ+3

2
⌋. Then it remains to prove that

κ ≥ δ − λ + 2, c ≥ δ − λ + 1 ⇒ c ≥ λ(δ − λ + 2)
(
λ = δ, δ − 1, ...,

⌊
δ + 3

2

⌋)
. (4)

Put δ − λ + 2 = µ. By this notation, the statement (4) is equivalent to

κ ≥ µ c ≥ µ − 1 ⇒ c ≥ µ(δ − µ + 2)
(
µ = 2, 3, ...,

⌊
δ + 2

2

⌋)
, (5)

which follows from Theorem 2 immediately. So, (4) ≡ (5) ⇐ ”Theorem 2”. Theorem 8 is
proved.

Proof of Theorem 6. Let G be a graph with

κ ≥ min{λ, δ − λ + 2}, c ≥ λ − 1

for each 1 ≤ λ ≤ δ. We shall prove that c ≥ λ(δ−λ+2). Observing that min{λ−1, δ−λ+1} ≤
λ − 1, we can strengthen the condition c ≥ min{λ − 1, δ − λ + 1} in Theorem 8 to c ≥ λ − 1
and the result follows immediately. Theorem 6 is proved. .



Zh. Nikoghosyan 13

5. Conclusion

In 2009 [14], a minimum degree sufficient condition for large cycles in graphs is established
showing that the famous conjecture of Bondy principally is improvable. In the same paper,
a lower bound for the length of a longest cycle (the circumference) is derived showing that
the conjecture of Jung (reverse version of Bondys conjecture) principally is improvable as
well. In this note, two new analogous sufficient conditions for large cycles and two new lower
bounds for the circumference are derived inspiring four new improved versions of Bondys
and Jungs conjectures.

References

[1] J.C. Bermond, “On Hamiltonian walks”, Congressus Numerantium, vol.15, pp. 41-50,
1976.

[2] J.A. Bondy, “Large cycles in graphs”, Discrete Mathematics, vol. 1, pp. 121-131, 1971.

[3] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan, London
and Elsevier, New York, 1976.

[4] J.A. Bondy, Longest paths and cycles in graphs of high degree, Research Report CORR
80-16, Department of Combinatorics and Optimization, Faculty of Mathematics, Uni-
versity of Waterloo, Ontario, Canada, 14 pages, 1980.

[5] S. Chiba, M. Tsugaki and T. Yamashita, “Degree sum conditions for the circumference
of 4-connected graphs”, Discrete Math., vol. 333, pp. 66-83, 2014.

[6] G.A. Dirac, “Some theorems on abstract graphs”, Proc. London Math. Soc., vol. 2, pp.
69-81, 1952.

[7] G. Fan, Extremal theorems on paths and cycles in graphs and weighted graphs, PhD
thesis, University of Waterloo, 1987.

[8] P. Fraisse and H.A. Jung, “Longest cycles and independent sets in k-connected graphs”,
Recent Studies in Graph Theory, Vischwa Internat. Publ., Gulbarga, India, pp. 114-139,
1989.

[9] H.A. Jung and H.A. Jung, “Longest cycles in graphs with moderate connectivity”, Top-
ics in Combinatorics and Graph Theory, Essays in Honour of Gerhard Ringel, Physica-
Verlag, Heidelberg, pp. 765778, 1990.

[10] H.A. Jung, “Degree bounds for long paths and cycles in k-connected graphs”, Com-
putational Discrete Mathematics, Lecture Notes in Comput. Sci., Springer, Berlin, vol.
2122, pp. 56-60, 2001.

[11] N. Linial, “A lower bound on the circumference of a graph”, Discrete Math., vol. 15,
pp. 297-300, 1976.

[12] C.St.J.A. Nash-Williams, “Edge-disjoint hamiltonian cycles in graphs with vertices of
large valency”, Studies in Pure Mathematics, Academic Press, San Diego, London, pp.
157-183, 1971.

[13] Zh. G. Nikoghosyan, “Cycle-Extensions and long cycles in graphs”, Transactions of the
Institute for Informatics and Automation Problems (IIAP) of NAS of RA, Mathematical
Problems of Computer Science, vol. 21, pp. 121-128, 2000.



1 4 A Note on Large Cycles in Graphs Around Conjectures of Bondy and Jung

[1 4 ] 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 is-
crete M athematics, vo l. 3 0 9 , p p . 1 9 2 5 -1 9 3 0 , 2 0 0 9 .

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

[1 6 ] H .-J. V o s s a n d C. Zu lu a g a , \ Ma xim a le g e r a d e u n d u n g e r a d e K r e is e in Gr a p h e n " , I,
W is s . Z. Te c h n . H o c h s c h u le Ilm e n a u , vo l. 4 , p p . 5 7 -7 0 , 1 9 7 7 .

[1 7 ] 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 Univ. Nat. Sci.,
vo l. 2 , p p . 8 -1 1 , 1 9 8 7 .

²ÏݳñÏ ·ñ³ýÝ»ñáõÙ Ù»Í óÇÏÉ»ñÇ Ù³ëÇÝ ´áݹÇÇ ¨ ÚáõÝ·Ç
í³ñϳÍÝ»ñÇ ßáõñç

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

ÐÐ ¶²² ÆÝýáñÙ³ïÇϳÛÇ ¨ ³íïáÙ³ï³óÙ³Ý åñáµÉ»ÙÝ»ñÇ ÇÝëïÇïáõï, ºñ¨³Ý, г۳ëï³Ý

e-mail: zhora@iiap.sci.am

²Ù÷á÷áõÙ

êï³óí»É »Ý Ýáñ µ³í³ñ³ñ å³ÛÙ³ÝÝ»ñ ·ñ³ýÇ ÁݹѳÝñ³óí³Í óÇÏÉ»ñÇ Ñ³Ù³ñ
(Áݹ·ñÏ»Éáí гÙÇÉÃáÝÛ³Ý ¨ ¹áÙÇݳÝï óÇÏÉ»ñÁ áñå»ë Ù³ëݳíáñ ¹»åù»ñ) ϳٳ۳ϳÝ
k-ϳå³Ïóí³Í ( k = 1 ; 2 ; ::: ) ·ñ³ýáõÙ, áñáÝù ³å³óáõóáõÙ »Ý ´áݹÇÇ (1980) ѳÛïÝÇ
í³ñϳÍÇ ×ßÙ³ñï³óÇáõÃÛáõÝÁ áñáß ï³ñµ»ñ³ÏÝ»ñÇ ¹»åùáõÙ, ÇÝãÇ ßÝáñÑÇí ½·³ÉÇáñ»Ý
ɳí³óíáõÙ ¿ ïíÛ³É í³ñϳÍáí ³ÏÝϳÉíáÕ ³ñ¹ÛáõÝùÁ: гٳÝÙ³Ýáñ»Ý, ³Ù»Ý³»ñϳñ
óÇÏÉÇ »ñϳñáõÃÛ³Ý Ñ³Ù³ñ ëï³óí»É »Ý Ýáñ ëïáñÇÝ ·Ý³Ñ³ï³Ï³ÝÝ»ñ ѳϳ¹³ñÓ
í³ñϳÍÇ Ñ³Ù³ñ, áñÝ ³é³ç ¿ ù³ß»É ÚáõÝ·Á 2001-ÇÝ: êï³óí³Í ³ñ¹ÛáõÝùÝ»ñÁ µ³í³ñ³ñ
ÑÇÙù»ñ »Ý ï³ÉÇë ³é³ç ù³ß»Éáõ Ýáñ ɳí³óí³Í ï³ñµ»ñ³ÏÝ»ñ ´áݹÇÇ ¨ ÚáõÝ·Ç
ݳËÝ³Ï³Ý í³ñϳÍÝ»ñÇ ÷á˳ñ»Ý:

Çàìåòêà î áîëüøèõ öèêëàõ â ãðàôàõ âîêðóã
ãèïîòåç Áîíäè è Þíãà

Æîðà Ã. Íèêîãîñÿí

Èíñòèòóò ïðîáëåì èíôîðìàòèêè è àâòîìàòèçàöèè ÍÀÍ ÐÀ, Åðåâàí, Àðìåíèÿ
e-mail: zhora@iiap.sci.am

Àííîòàöèÿ

Ïîëó÷åíû íîâûå äîñòàòî÷íûå óñëîâèÿ äëÿ îáîáùåííûõ öèêëîâ (âêëþ÷àÿ
ãàìèëüòîíîâûå è äîìèíàíòíûå öèêëû êàê ÷àñòíûå ñëó÷àè) â ïðîèçâîëüíîì k-

´³Ý³ÉÇ µ³é»ñ` гÙÇÉÃáÝÇ óÇÏÉ, ¹áÙÇݳÝï óÇÏÉ, ³Ù»Ý³»ñϳñ óÇÏÉ, Ù»Í óÇÏÉ:



Zh. Nikoghosyan 1 5

ñâÿçíîì ãðàôå ( k = 1 ; 2 ; ::: ) , äîêàçûâàþùèå ñïðàâåäëèâîñòü èçâåñòíîé ãèïîòåçû
Áîíäè (1980) äëÿ íåêîòîðûõ âàðèàíòîâ, çíà÷èòåëüíî óëó÷øèâ îæèäàåìûé ïî
äàííîé ãèïîòåçå ðåçóëüòàò. Àíàëîãè÷íî, ïîëó÷åíû íîâûå íèæíèå îöåíêè äëÿ
äëèíû äëèííåéøåãî öèêëà ãðàôà äëÿ îáðàòíîé ãèïîòåçû, ïðåäëîæåííîé Þíãîì
(2001). Ïîëó÷åííûå ðåçóëüòàòû â ñî÷åòàíèè äàþò îñíîâàíèÿ âûäâèæåíèÿ íîâûõ
óëó÷øåííûõ âàðèàíòîâ äëÿ èñõîäíûõ ãèïîòåç Áîíäè è Þíãà.

Êëþ÷åâûå ñëîâà: Ãàìèëüòîíîâ öèêë, äîìèíàíòíûé öèêë, äëèííåéøèé öèêë,
áîëüøîé öèêë.


	01_NIKOGHOSYAN_59
	01