TY - JOUR
T1 - Relative length of long paths and cycles in graphs with large degree sums
AU - Enomoto, Hikoe
AU - van den Heuvel, Jan
AU - Kaneko, Atsushi
AU - Saito, Akira
PY - 1995
Y1 - 1995
N2 - 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.
AB - 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.
KW - IR-71177
U2 - 10.1002/jgt.3190200210
DO - 10.1002/jgt.3190200210
M3 - Article
SN - 0364-9024
VL - 201
SP - 213
EP - 225
JO - Journal of graph theory
JF - Journal of graph theory
IS - 2
ER -