# 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]

 Preview

148kB
 Abstract: A weighted graph is a graph in which each edge is assigned a non-negative 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 2-connected 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: BibTeXEndNoteHTML CitationReference Manager

Repository Staff Only: item control page

Metis ID: 141183