Existence of Δλ-cycles and Δλ-paths

Research output: Contribution to journalArticleAcademic

11 Citations (Scopus)
153 Downloads (Pure)


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 languageEnglish
Pages (from-to)499-507
JournalJournal of graph theory
Issue number4
Publication statusPublished - 1988


Dive into the research topics of 'Existence of Δλ-cycles and Δλ-paths'. Together they form a unique fingerprint.

Cite this