Heavy cycles in 2-connected weighted graphs with large weighted degree sums

Bing Chen; Shenggui Zhang; T. C.Edwin Cheng

doi:10.1007/978-3-540-72588-6_56

Heavy cycles in 2-connected weighted graphs with large weighted degree sums

Bing Chen, Shenggui Zhang, T. C.Edwin Cheng

School of Mathematics and Statistics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

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=1³ d^w (v_i) ≤ m, where v₁, v₂ and v₃ are 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.

Original language	English
Title of host publication	Computational Science - ICCS 2007 - 7th International Conference, Proceedings
Publisher	Springer Verlag
Pages	338-346
Number of pages	9
Edition	PART 3
ISBN (Print)	9783540725879
DOIs	https://doi.org/10.1007/978-3-540-72588-6_56
State	Published - 2007
Event	7th International Conference on Computational Science, ICCS 2007 - Beijing, China Duration: 27 May 2007 → 30 May 2007

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 3
Volume	4489 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	7th International Conference on Computational Science, ICCS 2007
Country/Territory	China
City	Beijing
Period	27/05/07 → 30/05/07

Keywords

Hamilton cycle
Induced claw (modified claw.)
Weighted graph

Access to Document

10.1007/978-3-540-72588-6_56

Cite this

Chen, B., Zhang, S., & Cheng, T. C. E. (2007). Heavy cycles in 2-connected weighted graphs with large weighted degree sums. In Computational Science - ICCS 2007 - 7th International Conference, Proceedings (PART 3 ed., pp. 338-346). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4489 LNCS, No. PART 3). Springer Verlag. https://doi.org/10.1007/978-3-540-72588-6_56

Chen, Bing ; Zhang, Shenggui ; Cheng, T. C.Edwin. / Heavy cycles in 2-connected weighted graphs with large weighted degree sums. Computational Science - ICCS 2007 - 7th International Conference, Proceedings. PART 3. ed. Springer Verlag, 2007. pp. 338-346 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 3).

@inproceedings{20676eb084bc454790b3c1f5d8058223,

title = "Heavy cycles in 2-connected weighted graphs with large weighted degree sums",

abstract = "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=13 dw (vi) ≤ m, where v1, v2 and v3 are 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.",

keywords = "Hamilton cycle, Induced claw (modified claw.), Weighted graph",

author = "Bing Chen and Shenggui Zhang and Cheng, {T. C.Edwin}",

year = "2007",

doi = "10.1007/978-3-540-72588-6_56",

language = "英语",

isbn = "9783540725879",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

number = "PART 3",

pages = "338--346",

booktitle = "Computational Science - ICCS 2007 - 7th International Conference, Proceedings",

edition = "PART 3",

note = "7th International Conference on Computational Science, ICCS 2007 ; Conference date: 27-05-2007 Through 30-05-2007",

}

Chen, B, Zhang, S & Cheng, TCE 2007, Heavy cycles in 2-connected weighted graphs with large weighted degree sums. in Computational Science - ICCS 2007 - 7th International Conference, Proceedings. PART 3 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 3, vol. 4489 LNCS, Springer Verlag, pp. 338-346, 7th International Conference on Computational Science, ICCS 2007, Beijing, China, 27/05/07. https://doi.org/10.1007/978-3-540-72588-6_56

Heavy cycles in 2-connected weighted graphs with large weighted degree sums. / Chen, Bing; Zhang, Shenggui; Cheng, T. C.Edwin.
Computational Science - ICCS 2007 - 7th International Conference, Proceedings. PART 3. ed. Springer Verlag, 2007. p. 338-346 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4489 LNCS, No. PART 3).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Heavy cycles in 2-connected weighted graphs with large weighted degree sums

AU - Chen, Bing

AU - Zhang, Shenggui

AU - Cheng, T. C.Edwin

PY - 2007

Y1 - 2007

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=13 dw (vi) ≤ m, where v1, v2 and v3 are 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=13 dw (vi) ≤ m, where v1, v2 and v3 are 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

U2 - 10.1007/978-3-540-72588-6_56

DO - 10.1007/978-3-540-72588-6_56

M3 - 会议稿件

AN - SCOPUS:38148999611

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

PB - Springer Verlag

T2 - 7th International Conference on Computational Science, ICCS 2007

Y2 - 27 May 2007 through 30 May 2007

ER -

Chen B, Zhang S, Cheng TCE. Heavy cycles in 2-connected weighted graphs with large weighted degree sums. In Computational Science - ICCS 2007 - 7th International Conference, Proceedings. PART 3 ed. Springer Verlag. 2007. p. 338-346. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 3). doi: 10.1007/978-3-540-72588-6_56

Heavy cycles in 2-connected weighted graphs with large weighted degree sums

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this