2014/06/15 by Zh. G. Nikoghosyan, Nikoghosyan, Zh. G.
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1406.3833
openalex publication_date 2014/06/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a graph G, n denotes the order of G, p the order of a longest path in G and c the order of a longest cycle. We show that if G is a 2-connected graph such that d(x)+d(y)+d(z)≥ p+2 for all triples x,y,z of independent vertices, then c≥ p-1. This improves results of Nash-Williams (in terms of minimum degree δ and order n), Bondy (in terms of degree sum σ3 and order n), and Enomoto, Heuvel, Kaneko and Saito (in terms of degree sum σ3, order n and relative length diff(G)=p-c).