On Relative Length of Long Paths and Cycles in Graphs

2014/07/30 by Nikoghosyan, Zh. G.
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1407.8129

Abstract

Let G be a graph on n vertices, p the order of a longest path and κ the connectivity of G. In 1989, Bauer, Broersma Li and Veldman proved that if G is a 2-connected graph with d(x)+d(y)+d(z)≥ n+κ for all triples x,y,z of independent vertices, then G is hamiltonian. In this paper we improve this result by reducing the lower bound n+κ to p+κ.

Related

• Relative Length of Long Paths and Cycles in Graphs
• My Research Visiting Card in Hamiltonian Graph Theory
• Cycles of many lengths in Hamiltonian graphs
• Longest cycles in vertex-transitive and highly connected graphs
• Long cycles in Hamiltonian graphs