Acta mathematica scientia,Series A

• Articles • Previous Articles     Next Articles

A Fan Type Theorem for Heavy Cycles in Weighted Graphs

Yu Rong1,2;Hu Zhiquan2   

  1. (1.School of Science, Wuhan Institute of Technology, Wuhan 430073; 2.Department of Mathematics and Statistics, Central China Normal University, Wuhan 430079)
  • Received:2006-03-08 Revised:2008-02-08 Online:2008-10-25 Published:2008-10-25
  • Contact: Yu Rong

Abstract: Let G=(V, E; w) be a weighted graph, and define the weighted degree dwG(v) of a vertex v in G as the sum of the weights of the edges incident with v. In this paper, the following theorem is proved: suppose G is a 2-connected weighted graph, where (i) w(xy)=w(yz) for every induced path xyz, and (ii) in every induced subgraph T of G isomorphic to K1,3 or K1,3+e, all the edges of T have the same weight and min{max{dwG(x), dwG(y)} : d(x,y) =2,x,y ∈ V(T)}≥ c/2, then G contains either a Hamilton cycle or a cycle of weight c at least. This
respectively generalizes three theorems of Fan[5], Bedrossian et al[2] and Zhang et al[7].

Key words: Semi-normal weighted graph, Heaviest longest path, Hamiltonian cycle, Weighted degree

CLC Number: 

  • 05C
Trendmd