Relative length of long paths and cycles in graphs with large degree sums

Share/Save/Bookmark

Enomoto, Hikoe and Heuvel van den, Jan and Kaneko, Atsushi and Saito, Akira (1995) Relative length of long paths and cycles in graphs with large degree sums. Journal of Graph Theory, 201 (2). pp. 213-225. ISSN 0364-9024

[img]
Preview
PDF
581Kb
Abstract:For a graph G, p(G) denotes the order of a longest path in G and c(G) the order of a longest cycle. We show that if G is a connected graph n ≥ 3 vertices such that d(u) + d(v) + d(w) n for all triples u, v, w of independent vertices, then G satisfies c(G) ≥ p(G) - 1, or G is in one of six families of exceptional graphs. This generalizes results of Bondy and of Bauer, Morgana, Schmeichel, and Veldman.
Item Type:Article
Copyright:© 1995 Wiley InterScience
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Link to this item:http://purl.utwente.nl/publications/71177
Official URL:http://dx.doi.org/10.1002/jgt.3190200210
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page