### Abstract

Original language | English |
---|---|

Pages (from-to) | 213-225 |

Journal | Journal of graph theory |

Volume | 201 |

Issue number | 2 |

DOIs | |

Publication status | Published - 1995 |

### Fingerprint

### Keywords

- IR-71177

### Cite this

*Journal of graph theory*,

*201*(2), 213-225. https://doi.org/10.1002/jgt.3190200210

}

*Journal of graph theory*, vol. 201, no. 2, pp. 213-225. https://doi.org/10.1002/jgt.3190200210

**Relative length of long paths and cycles in graphs with large degree sums.** / Enomoto, Hikoe; van den Heuvel, Jan; Kaneko, Atsushi; Saito, Akira.

Research output: Contribution to journal › Article › Academic

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

VL - 201

SP - 213

EP - 225

JO - Journal of graph theory

JF - Journal of graph theory

SN - 0364-9024

IS - 2

ER -