# A type condition for heavy cycles in weighted graphs

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

 Preview

135kB
 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. The weighted degree sum of any three independent vertices is at least ; 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 Fournier and Fraisse on the existence of long cycles in -connected unweighted graphs in the case . Our proof of the above result also suggests a new proof to the theorem of Fournier and Fraisse in the case . Item Type: Report Faculty: Electrical Engineering, Mathematics and Computer Science (EEMCS) Research Group: Link to this item: http://purl.utwente.nl/publications/65702 Export this item as: BibTeXEndNoteHTML CitationReference Manager

Repository Staff Only: item control page

Metis ID: 141192