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

Bing Chen, Shenggui Zhang, Edwin Tai Chiu Cheng

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

1 Citation (Scopus)

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=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.
Original languageEnglish
Title of host publicationComputational Science - ICCS 2007 - 7th International Conference, Proceedings
Pages338-346
Number of pages9
EditionPART 3
Publication statusPublished - 1 Dec 2007
Event7th International Conference on Computational Science, ICCS 2007 - Beijing, China
Duration: 27 May 200730 May 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 3
Volume4489 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference7th International Conference on Computational Science, ICCS 2007
CountryChina
CityBeijing
Period27/05/0730/05/07

Keywords

  • Hamilton cycle
  • Induced claw (modified claw.)
  • Weighted graph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this