A Note on Large Cycles in Graphs Around Conjectures of Bondy and Jung
DOI:
https://doi.org/10.51408/1963-0097Keywords:
Hamilton cycle, Dominating cycle, Longest cycle, Large cycleAbstract
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 significantly 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.
References
J.C. Bermond, “On Hamiltonian walks”, Congressus Numerantium, vol.15, pp. 41-50, 1976.
J.A. Bondy, “Large cycles in graphs”, Discrete Mathematics, vol. 1, pp. 121-131, 1971.
J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan, London and Elsevier, New York, 1976.
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, University of Waterloo, Ontario, Canada, 14 pages, 1980.
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.
G.A. Dirac, “Some theorems on abstract graphs”, Proc. London Math. Soc., vol. 2, pp. 69-81, 1952.
G. Fan, Extremal theorems on paths and cycles in graphs and weighted graphs, PhD thesis, University of Waterloo, 1987.
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.
H.A. Jung and H.A. Jung, “Longest cycles in graphs with moderate connectivity”, Topics in Combinatorics and Graph Theory, Essays in Honour of Gerhard Ringel, Physica-Verlag, Heidelberg, pp. 765778, 1990.
H.A. Jung, “Degree bounds for long paths and cycles in k-connected graphs”, Computational Discrete Mathematics, Lecture Notes in Comput. Sci., Springer, Berlin, vol. 2122, pp. 56-60, 2001.
N. Linial, “A lower bound on the circumference of a graph”, Discrete Math., vol. 15, pp. 297-300, 1976.
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.
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.
Zh .G. Nikoghosyan, “Dirac-type generalizations concerning large cycles in graphs", Discrete Mathematics, vol. 309, pp. 1925-1930, 2009.
O. Ore, “A note on Hamiltonian circuits", Amer. Math. Monthly, vol. 67, p. 55, 1960.
H.-J. Vossand C. Zuluaga, „Maximale gerade und ungerade Kreise in Graphen", I, Wiss. Z. Techn. Hochschule Ilmenau, vol. 4, pp. 57-70, 1977.
Y. Zou, „A generalization of a theorem of Jung", J. Nanjing Normal Univ. Nat. Sci., vol. 2, pp. 8-11, 1987.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Zhora G. Nikoghosyan
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
