TY - GEN

T1 - An Implicit Weighted Degree Condition for Heavy Cycles in Weighted Graphs

AU - Chen, Bing

AU - Zhang, Shenggui

AU - Cheng, Edwin Tai Chiu

PY - 2007/12/1

Y1 - 2007/12/1

N2 - Let G be a 2-connected weighted graph and m a nonnegative number. As introduced by Li as the weighted analogue of a concept due to Zhu et al, we use idw(v) to denote the implicit weighted degree of a vertex v in G. In this paper we prove that G contains either a Hamilton cycle or a cycle of weight at least m, if the following two conditions are satisfied: (1) max {idw(u), idw(v)}≥ m/2 for each pair of nonadjacent vertices u and v that are vertices of an induced claw or an induced modified claw of G; (2) In each induced claw, each induced modified claw and each induced P4of G, all the edges have the same weight. This is a common generalization of several previous results on the existence of long cycles in unweighted graphs and heavy cycles in weighted graphs.

AB - Let G be a 2-connected weighted graph and m a nonnegative number. As introduced by Li as the weighted analogue of a concept due to Zhu et al, we use idw(v) to denote the implicit weighted degree of a vertex v in G. In this paper we prove that G contains either a Hamilton cycle or a cycle of weight at least m, if the following two conditions are satisfied: (1) max {idw(u), idw(v)}≥ m/2 for each pair of nonadjacent vertices u and v that are vertices of an induced claw or an induced modified claw of G; (2) In each induced claw, each induced modified claw and each induced P4of G, all the edges have the same weight. This is a common generalization of several previous results on the existence of long cycles in unweighted graphs and heavy cycles in weighted graphs.

UR - http://www.scopus.com/inward/record.url?scp=49949119475&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-70666-3_3

DO - 10.1007/978-3-540-70666-3_3

M3 - Conference article published in proceeding or book

SN - 3540706658

SN - 9783540706656

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 21

EP - 29

BT - Discrete Geometry, Combinatorics and Graph Theory 7th China-Japan Conference, CJCDGCGT 2005, Tianjin, China, November 18-20, 2005, Xi'an, China, November 22-24, 2005, Revised Selected Papers

T2 - 7th China-Japan Conference on Discrete Geometry, Combinatorics and Graph Theory, CJCDGCGT 2005

Y2 - 22 November 2005 through 24 November 2005

ER -