Existence of Δλ-cycles and Δλ-paths

Research output: Contribution to journalArticleAcademic

10 Citations (Scopus)
69 Downloads (Pure)

Abstract

A Cycle C of a graph G is called a Dλ-cycle if every component of G - V(C) has order less than λ A Dλ-path is defined analogously. Dλ-cycles and Dλ-paths were introduced by Veldman. Here a cycle C of a graph G is called a Δλ-cycle if all vertices of G are at distance less than λ from a vertex of C. A Δλ-path is defined analogously. In particular, in a connected graph, a Δλ-cycle is a Δλ-Cycle and a Δλ-Path is a Δλ-path. Furthermore, a Δ1-cycle is a Hamilton cycle and a Δ1path is a Hamilton path. Necessary conditions and sufficient conditions are derived for graphs to have a Δλ-cycle or Δλ-path. The results are analogues of theorems on Dλ-cycles and Dλ-paths. In particular, a result of Chvátal and Erdös on Hamilton cycles and Hamiiton paths is generalized. A recent conjecture of Bondy and Fan is settled.
Original languageUndefined
Pages (from-to)499-507
JournalJournal of graph theory
Volume12
Issue number4
DOIs
Publication statusPublished - 1988

Keywords

  • IR-70848

Cite this