Degree Sums for Edges and Cycle Lengths in Graphs

摘要

Let G be a graph of order n satisfying d(u) + d(v) > = n for every edge uv of G.We show that the circumference--the length of a longest cycle--of G can be expressed in terms of a certain graph parameter, and can be computed in polynomial time. Moreover, we show that G contains cycles of every length between 3 and the circumference, unless G is complete bipartite.