Premium
Relative length of long paths and cycles in graphs with large degree sums
Author(s) -
Enomoto Hikoe,
van den Heuvel Jan,
Kaneko Atsushi,
Saito Akira
Publication year - 1995
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190200210
Subject(s) - combinatorics , mathematics , graph , degree (music) , bound graph , induced path , order (exchange) , discrete mathematics , graph power , chordal graph , longest path problem , line graph , physics , acoustics , finance , economics
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. © 1995, John Wiley & Sons, Inc.