A fan type condition for heavy cycles in weighted graphs
Broersma, H.J. and Zhang, S. and Li , X. and Wang, L. (2000) A fan type condition for heavy cycles in weighted graphs. [Report]

PDF
148kB 
Abstract:  A weighted graph is a graph in which each edge is assigned a nonnegative number , called the weight of . The weight of a cycle is the sum of the weights of its edges. The weighted degree of a vertex is the sum of the weights of the edges incident with . In this paper, we prove the following result: Suppose is a 2connected weighted graph which satisfies the following conditions: 1. ; 2. for every vertex with ; 3. In every triangle of , either all edges of have different weights or all edges of have the same weight. Then contains either a Hamilton cycle or a cycle of weight at least . This generalizes a theorem of Fan on the existence of long cycles in unweighted graphs to weighted graphs. We also show we cannot omit Condition 2 or 3 in the above result.

Item Type:  Report 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/65701 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page
Metis ID: 141183