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

Enomoto Hikoe | Zendy; van den Heuvel Jan | Zendy; Kaneko Atsushi | Zendy; Saito Akira | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research