Existence of Δλ‐cycles and Δλ‐paths
Hajo J. Broersma · Journal of Graph Theory · 1988
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.