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. If G is 1-tough then it is pancyclic or G = Kr,r with r = n/2.
|Number of pages||4|
|Journal||Journal of graph theory|
|Publication status||Published - 1997|
Brandt, S., & Veldman, H. J. (1997). Degree sums for edges and cycle lengths in graphs. Journal of graph theory, 25(4), 253-256. https://doi.org/10.1002/(SICI)1097-0118(199708)25:4<253::AID-JGT2>3.0.CO;2-J