### 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 language | Undefined |
---|---|

Pages (from-to) | 499-507 |

Journal | Journal of graph theory |

Volume | 12 |

Issue number | 4 |

DOIs | |

Publication status | Published - 1988 |

### Keywords

- IR-70848

## Cite this

Broersma, H. J. (1988). Existence of Δλ-cycles and Δλ-paths.

*Journal of graph theory*,*12*(4), 499-507. https://doi.org/10.1002/jgt.3190120405