On Long Cycles in Graphs in Terms of Degree Sequences

Abstract

Let G be a graph on n vertices with degree sequence δ = d1≤d2≤...≤.dn. Let m be the number of connected components of G, c the circumference - the order of a longest cycle, p the order of a longest path in G and σ8 the minimum degree sum of an independent set of s vertices. In this paper it is shown that in every graph G, c≥dσm+m + 1. This bound is best possible and generalizes the earliest lower bound for the circumference due to Dirac (1952): c≥ δ + 1 = d1 + 1. As corollaries, we have: (i) c≥d δ +1 + 1; (ii) if dσm+m+m≥p -1, then c = p; (iii) if G is a connected graph withdδ+1≥p -1, then G is hamiltonian; (iv) if dσm+m+m≥n-1,then G is hamiltonian.