Degree sums for edges and cycle lengths in graphs


Brandt, Stephan and Veldman, Henk Jan (1997) Degree sums for edges and cycle lengths in graphs. Journal of Graph Theory, 25 (4). pp. 253-256. ISSN 0364-9024

Abstract: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.
Item Type:Article
Copyright:© 1997 Wiley InterScience
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:<253::AID-JGT2>3.0.CO;2-J
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 140776