A Fan Type Theorem For Heavy Cycles In Weighted Graphs

Suppose that G = (V, E; w) is a weighted graph, define the weighted degree d_G^w(v) of a vertex v in G as the sum of the weights of the edges incident with v, and the weight of a cycle is defined as the sum of the weights of its edges. The following theorem is a well-known result of Fan Genghua [7]: Let G be a 2-connected graph on n vertices and 3 < c < n, ifd(v, u) = 2 max{d(v), d(u)} ≥ c/2for each pair of vertices v and u in G, then G contains either a Hamilton cycle or a cycle of length at least c. Bedrossian et al [1] and Zhang et al [12] have respectively given two generalizations of Fan's theorem. In this paper, we give a further generalization of Fan's theorem as follows:Let G be a 2-connected weighted graph which satisfies the following conditions,(1) for every induced subgraph T of G isomorphic to K_1,3, all the edges of T have the same weight;(2) for every induced subgraph T of G isomorphic to K_1,3 + e, all the edges of T have the same weight;(3) for every induced subgraph T of G isomorphic to K_1,3 or K_1,3 + e,rnin{max{d_H^w(x),d_G^w(y)} : d(x,y) = 2,x,y ∈ V(T)} ≥ c/2.Then G contains either a Hamilton cycle or a cycle of weight at least c.In addition, we also prove that the conditions (1) and (2) of the above theorem can not be weakened to condition (1) or condition (2).