A fan type condition for heavy cycles in weighted graphs

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

Research output: Contribution to journalArticleAcademicpeer-review

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 d w (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. max{d w (x),d w (y)∣d(x,y)=2}≥c/2; 2. w(x z)=w(y z) 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 c. This generalizes a theorem of Fan on the existence of long cycles in unweighted graphs to weighted graphs. We also show we cannot omit Condition 2 or 3 in the above result.
Original languageEnglish
Pages (from-to)193-200
Number of pages8
JournalGraphs and combinatorics
Volume18
Issue number1
DOIs
Publication statusPublished - 2002

Keywords

  • METIS-206787
  • IR-96374

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

Cite this