Journal or Publication Title:
Date of publication:
Volume:
ISSN:
Additional Information:
Title:
On Long Cycles in Graphs in Terms of Degree Sequences
Other title:
Creator:
Subject:
Uncontrolled Keywords:
Hamilton cycle ; Longest cycle ; Circumference ; Minimum degree ; Degree sequence
Coverage:
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 ¾s the minimum degree sum of an independent set of s vertices. In this paper it is shown that in every graph G, c ≥ dm+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 ≥p-1, then c = p; (iii) if G is a connected graph with d±+1≥p-1, then G is hamiltonian; (iv) if dσm+m ≥ n - 1, then G is hamiltonian.