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 -