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

Hikoe Enomoto, Jan van den Heuvel, Atsushi Kaneko, Akira Saito

Research output: Contribution to journalArticleAcademic

20 Citations (Scopus)
68 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)213-225
JournalJournal of graph theory
Volume201
Issue number2
DOIs
Publication statusPublished - 1995

Fingerprint

Degree Sum
Long Cycle
Longest Path
Graph in graph theory
Connected graph
Denote
Generalise
Family

Keywords

  • IR-71177

Cite this

Enomoto, Hikoe ; van den Heuvel, Jan ; Kaneko, Atsushi ; Saito, Akira. / Relative length of long paths and cycles in graphs with large degree sums. In: Journal of graph theory. 1995 ; Vol. 201, No. 2. pp. 213-225.
@article{4085b3f101df4e1a93249abe9780b5cf,
title = "Relative length of long paths and cycles in graphs with large degree sums",
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.",
keywords = "IR-71177",
author = "Hikoe Enomoto and {van den Heuvel}, Jan and Atsushi Kaneko and Akira Saito",
year = "1995",
doi = "10.1002/jgt.3190200210",
language = "English",
volume = "201",
pages = "213--225",
journal = "Journal of graph theory",
issn = "0364-9024",
publisher = "Wiley-Liss Inc.",
number = "2",

}

Enomoto, H, van den Heuvel, J, Kaneko, A & Saito, A 1995, 'Relative length of long paths and cycles in graphs with large degree sums' 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.

In: Journal of graph theory, Vol. 201, No. 2, 1995, p. 213-225.

Research output: Contribution to journalArticleAcademic

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 -