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]

PDF
135kB 
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. 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:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page
Metis ID: 141192