On Some Versions of Conjectures of Bondy and Jung
Keywords:
Hamilton cycle, Dominating cycle, Long cycles, Bondy's conjecture, Jung's ConjectureAbstract
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.
References
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.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
