A $\sigma_3$ type condition for heavy cycles in weighted graphs

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

Preview

PDF
132Kb

Abstract:	A weighted graph is a graph in which each edge $e$ is assigned a non-negative number $w(e)$ , called the weight of $e$ . The weight of a cycle is the sum of the weights of its edges. The weighted degree $d^w(v)$ of a vertex $v$ is the sum of the weights of the edges incident with $v$ . In this paper, we prove the following result: Suppose $G$ is a 2-connected weighted graph which satisfies the following conditions: 1. The weighted degree sum of any three independent vertices is at least $m$ ; 2. $w(xz)=w(yz)$ for every vertex $z\in N(x)\cap N(y)$ with $d(x,y)=2$ ; 3. In every triangle $T$ of $G$ , either all edges of $T$ have different weights or all edges of $T$ have the same weight. Then $G$ contains either a Hamilton cycle or a cycle of weight at least $2m/3$ . This generalizes a theorem of Fournier and Fraisse on the existence of long cycles in $k$ -connected unweighted graphs in the case $k=2$ . Our proof of the above result also suggests a new proof to the theorem of Fournier and Fraisse in the case $k=2$ .
Item Type:	Report
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/65702
Export this item as:	BibTeX EndNote HTML Citation Reference Manager