Existence of Δλ-cycles and Δλ-paths

Share/Save/Bookmark

Broersma, H.J. (1988) Existence of Δλ-cycles and Δλ-paths. Journal of Graph Theory, 12 (4). pp. 499-507. ISSN 0364-9024

[img]
Preview
PDF
382Kb
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.
Item Type:Article
Copyright:© 1988 Wiley InterScience
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/70848
Official URL:http://dx.doi.org/10.1002/jgt.3190120405
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page