Claw Conditions for Heavy Cycles in Weighted Graphs |
| |
Authors: | Jun Fujisawa |
| |
Affiliation: | (1) Department of Mathematics, Keio University, Yokohama 223-8522, Japan |
| |
Abstract: | A graph is called a weighted graph when each edge e is assigned a nonnegative number w(e), called the weight of e. For a vertex v of a weighted graph, dw(v) is the sum of the weights of the edges incident with v. For a subgraph H of a weighted graph G, the weight of H is the sum of the weights of the edges belonging to H. In this paper, we give a new sufficient condition for a weighted graph to have a heavy cycle. A 2-connected weighted graph G contains either a Hamilton cycle or a cycle of weight at least c, if G satisfies the following conditions: In every induced claw or induced modified claw F of G, (1) max{dw(x),dw(y)} c/2 for each non-adjacent pair of vertices x and y in F, and (2) all edges of F have the same weight. |
| |
Keywords: | Weighted graph Heavy cycle Fan-type condition Claw Modified claw |
本文献已被 SpringerLink 等数据库收录! |
|