Back to University of Twente portal
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
![[img]](http://doc.utwente.nl/style/images/fileicons/application_pdf.png)
| PDF 63Kb |
| 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 |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page
Metis ID: 140776