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

    24 Citations (Scopus)
    172 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

    Keywords

    • IR-71177

    Fingerprint

    Dive into the research topics of 'Relative length of long paths and cycles in graphs with large degree sums'. Together they form a unique fingerprint.

    Cite this