On Longest Cycles in 2-connected Graphs
Keywords:
Hamilton cycle, Dominating cycle, Longest cycle, Longest path, Minimum degree, Degree sumsAbstract
For a graph G, n denotes the order (the number of vertices) of G, c the order of a longest cycle in G (called circumference), p the order of a longest path and ± the minimum degree. In 1952, Dirac proved: (i) if G is a 2-connected graph, then c ¸ minfn; 2±g. The bound 2± in (i) was enlarged independently by Bondy (1971), Bermond (1976) and Linial (1976) in terms of ¾2 - the minimum degree sum of two nonadjacent vertices: (ii) if G is a 2-connected graph, then c ¸ minfn; ¾2g. In this paper two further extensions of (i) and (ii) are presented by incorporating p and the length of a vine on a longest path of G as new parameters along with n, ± and ¾2.
References
J.A.Bondy, Large cycles in graphs", Discrete Math., vol.1, pp. 121-131, 1971.
J. A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macm illan, London and Elsevier, New York, 1976.
J. C. Bermond, On Hamiltonian walks", Congr Numer, vol. 15, pp. 41-51, 1976.
G.A. Dirac, Some theorems on abstract graphs", Proc. London, Math. Soc., vol. 2, pp. 69-81, 1952.
N.Linial, A lower bound on the circumference of a graph", Discrete Math., vol. 15, pp. 297-300, 1976
K. Ozeki and T. Yamashita, Length of longest cycles in a graph whose relative length is at least two", Graphs and Combin., vol. 28, pp. 859-868, 2012.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
