A sigma 3 type condition for heavy cycles in weighted graphs

Haitze J. Broersma, Shenggui Zhang, Xueliang Li, Xueliang Li

Research output: Contribution to journalArticleAcademicpeer-review

36 Downloads (Pure)

Abstract

A weighted graph is a graph in which each edge e is assigned a non-negative number w(e), called the weight of e. The weight of a cycle is the sum of the weights of its edges. The weighted degree dw(v) of a vertex v is the sum of the weights of the edges incident with v. In this paper, we prove the following result: Suppose G is a 2-connected weighted graph which satisfies the following conditions: 1. The weighted degree sum of any three independent vertices is at least m; 2. w(xz)=w(yz) for every vertex z∈N(x)∩ N(y) with d(x,y)=2; 3. In every triangle T of G, either all edges of T have different weights or all edges of T have the same weight. Then G contains either a Hamilton cycle or a cycle of weight at least 2m/3. This generalizes a theorem of Fournier and Fraisse on the existence of long cycles in k-connected unweighted graphs in the case k=2. Our proof of the above result also suggests a new proof to the theorem of Fournier and Fraisse in the case k=2.
Original languageEnglish
Pages (from-to)159-166
Number of pages8
JournalDiscussiones mathematicae. Graph theory
Volume21
Issue number2
DOIs
Publication statusPublished - 2001

Keywords

  • METIS-201544
  • IR-96371

Fingerprint Dive into the research topics of 'A sigma 3 type condition for heavy cycles in weighted graphs'. Together they form a unique fingerprint.

Cite this