TY - GEN
T1 - Heavy cycles in 2-connected weighted graphs with large weighted degree sums
AU - Chen, Bing
AU - Zhang, Shenggui
AU - Cheng, Edwin Tai Chiu
PY - 2007/12/1
Y1 - 2007/12/1
N2 - In this paper, we prove that a 2-connected weighted graph G contains either a Hamilton cycle or a cycle of weight at least 2m/3 if it satisfies the following conditions: (1) Σi=13dw(vi) ≤ m, where v1, v2and v3are three pairwise nonadjacent vertices of G, and two of them are nonadjacent vertices of an induced claw or an induced modified claw; (2) In each induced claw and each induced modified claw of G, all edges have the same weight. This extends several previous results on the existence of heavy cycles in weighted graphs.
AB - In this paper, we prove that a 2-connected weighted graph G contains either a Hamilton cycle or a cycle of weight at least 2m/3 if it satisfies the following conditions: (1) Σi=13dw(vi) ≤ m, where v1, v2and v3are three pairwise nonadjacent vertices of G, and two of them are nonadjacent vertices of an induced claw or an induced modified claw; (2) In each induced claw and each induced modified claw of G, all edges have the same weight. This extends several previous results on the existence of heavy cycles in weighted graphs.
KW - Hamilton cycle
KW - Induced claw (modified claw.)
KW - Weighted graph
UR - http://www.scopus.com/inward/record.url?scp=38148999611&partnerID=8YFLogxK
M3 - Conference article published in proceeding or book
SN - 9783540725879
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 338
EP - 346
BT - Computational Science - ICCS 2007 - 7th International Conference, Proceedings
T2 - 7th International Conference on Computational Science, ICCS 2007
Y2 - 27 May 2007 through 30 May 2007
ER -