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

Bing Chen, Shenggui Zhang, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

Abstract

A weighted graph is one in which every edge e is assigned a nonnegative number w (e), called the weight of e. The weight of a cycle is defined as the sum of the weights of its edges. The weighted degree of a vertex is the sum of the weights of the edges incident with it. In this paper, we prove that: Let G be a k-connected weighted graph with k ≥ 2. Then G contains either a Hamilton cycle or a cycle of weight at least 2 m / (k + 1), if G satisfies the following conditions: (1) The weighted degree sum of any k + 1 pairwise nonadjacent vertices is at least m; (2) In each induced claw and each induced modified claw of G, all edges have the same weight. This generalizes an early result of Enomoto et al. on the existence of heavy cycles in k-connected weighted graphs.
Original languageEnglish
Pages (from-to)4531-4543
Number of pages13
JournalDiscrete Mathematics
Volume308
Issue number20
DOIs
Publication statusPublished - 28 Oct 2008

Keywords

  • Heavy cycle
  • Induced claw (modified claw)
  • Weighted degree (sum)

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Cite this