An Implicit Weighted Degree Condition for Heavy Cycles in Weighted Graphs

Bing Chen, Shenggui Zhang, Edwin Tai Chiu Cheng

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

2 Citations (Scopus)

Abstract

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.
Original languageEnglish
Title of host publicationDiscrete 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
Pages21-29
Number of pages9
DOIs
Publication statusPublished - 1 Dec 2007
Event7th China-Japan Conference on Discrete Geometry, Combinatorics and Graph Theory, CJCDGCGT 2005 - Xi'an, China
Duration: 22 Nov 200524 Nov 2005

Publication series

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

Conference

Conference7th China-Japan Conference on Discrete Geometry, Combinatorics and Graph Theory, CJCDGCGT 2005
CountryChina
CityXi'an
Period22/11/0524/11/05

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this