Degree sums for edges and cycle lengths in graphs

Share/Save/Bookmark

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

open access
[img]
Preview
PDF
65kB
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
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/71423
Official URL:http://dx.doi.org/10.1002/(SICI)1097-0118(199708)25:4<253::AID-JGT2>3.0.CO;2-J
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 140776