科研之友
微信
新浪微博
Facebook
分享链接
摘要
A weighted graph is a graph in which each edge a 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: I. max{d(w)(x),d(w)(y) \ d(x, y) = 2} greater than or equal to c/2; 2. w(xz) = w(yz) for every vertex z is an element of N(x) boolean AND 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 c. 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.
- 出版日期2002
- 单位西北工业大学
