On Some Versions of Conjectures of Bondy and Jung


  • Zhora G. Nikoghosyan Institute for Informatics and Automation Problems of NAS RA


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


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 k ≤ 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.


J. A. Bondy, “Longest paths and cycles in graphs of high degree", Research Report CORR 80-16. University of Waterloo, Waterloo, Ontario, 1980.

H. A. Jung, “Degree bounds for long paths and cycles in k-connected graphs",in Computational Discrete Mathematics, Lecture Notes in Computer Science, Springer, Berlin, vol. 2122, pp. 56-60, 2001.

G. A. Dirac, “Some theorems on abstract graphs", Proceedings of the London Mathematical Society, vol. 2, pp. 69-81, 1952.

O. Ore, “A note on hamiltonian circuits", American Mathematical Monthly, vol. 67, p. 55, 1960.

C. St. J. A. Nash-Williams, “Edge-disjoint hamiltonian cycles in graphs with vertices of large valency", in: L. Mirsky, ed., "Studies in Pure Mathematics", Academic Press, San Diego/London, pp. 157-183, 1971.

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

P. Fraisse and H. A. Jung, “Longest cycles and independent sets in k-connected graphs", in V.R. Kulli. ed., Recent Studies in Graph Theory, (Vischwa International Publishing Gulbarga, India, pp. 114-139, 1989.

H. A. Jung, “On maximal circuits in finite graphs", Annals of Discrete Mathematics, vol. 3, pp. 129-144, 1978.

H. A. Jung, “Longest circuits in 3-connected graphs", Colloquium Mathematical Society Janos Bolyai 37, Finite and Infinite sets, Eger, pp. 403-438, 1981.

Zh. G. Nikoghosyan, “Dirac-type generalizations concerning large cycles in graphs", Discrete Mathematics, vol. 309, no. 8, pp. 1925-1930, 2009.

Zh. G. Nikoghosyan, “Advanced Lower Bounds for the Circumference", Graphs and Combinatorics, vol. 29, no. 5, pp. 1531-1541, 2013.

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

Y. Zou, “A generalization of a theorem of Jung", J. Nanjing Normal University Natural Science E dition, vol. 2, pp. 8-11, 1987.

J. C. Bermond, “On hamiltonian walks", Congressus Numerantium, vol. 15, pp. 41-51, 1976.

N. Linial, “A lower bound on the circumference of a graph", Discrete Mathematics, vol. 15, no. 3, pp. 297-300, 1976.




How to Cite

Nikoghosyan, Z. G. . (2021). On Some Versions of Conjectures of Bondy and Jung. Mathematical Problems of Computer Science, 45, 19–26. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/161