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

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

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

Show download statistics for this publication

Repository Staff Only: item control page