Existence of Δλcycles and Δλpaths
Broersma, H.J. (1988) Existence of Δλcycles and Δλpaths. Journal of Graph Theory, 12 (4). pp. 499507. ISSN 03649024

PDF
391kB 
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 Δ1cycle 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