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 -