A fan type condition for heavy cycles in weighted graphs

Hajo Broersma, Shenggui Zhang, Xueliang Li, Ligong Wang

Research output: Book/ReportReportProfessional

8 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 $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)\mid d(x,y)=2\}\geq c/2$; 2. $w(xz)=w(yz)$ for every vertex $z\in N(x)\cap 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
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages13
Publication statusPublished - 2000

Publication series

NameMemorandum Faculteit TW
PublisherUniversity of Twente
No.1513
ISSN (Print)0169-2690

Fingerprint

Weighted Graph
Cycle
Hamilton Cycle
Long Cycle
Graph in graph theory
Vertex of a graph
Fan
Connected graph
Triangle
Non-negative
Generalise
Theorem

Keywords

  • MSC-05C45
  • MSC-05C35
  • MSC-05C38

Cite this

Broersma, H., Zhang, S., Li, X., & Wang, L. (2000). A fan type condition for heavy cycles in weighted graphs. (Memorandum Faculteit TW; No. 1513). Enschede: University of Twente, Department of Applied Mathematics.
Broersma, Hajo ; Zhang, Shenggui ; Li, Xueliang ; Wang, Ligong. / A fan type condition for heavy cycles in weighted graphs. Enschede : University of Twente, Department of Applied Mathematics, 2000. 13 p. (Memorandum Faculteit TW; 1513).
@book{d01108e0d5854a07b7284acd678bcd5a,
title = "A fan type condition for heavy cycles in weighted graphs",
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)\mid d(x,y)=2\}\geq c/2$; 2. $w(xz)=w(yz)$ for every vertex $z\in N(x)\cap 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.",
keywords = "MSC-05C45, MSC-05C35, MSC-05C38",
author = "Hajo Broersma and Shenggui Zhang and Xueliang Li and Ligong Wang",
year = "2000",
language = "English",
series = "Memorandum Faculteit TW",
publisher = "University of Twente, Department of Applied Mathematics",
number = "1513",

}

Broersma, H, Zhang, S, Li, X & Wang, L 2000, A fan type condition for heavy cycles in weighted graphs. Memorandum Faculteit TW, no. 1513, University of Twente, Department of Applied Mathematics, Enschede.

A fan type condition for heavy cycles in weighted graphs. / Broersma, Hajo; Zhang, Shenggui; Li, Xueliang; Wang, Ligong.

Enschede : University of Twente, Department of Applied Mathematics, 2000. 13 p. (Memorandum Faculteit TW; No. 1513).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - A fan type condition for heavy cycles in weighted graphs

AU - Broersma, Hajo

AU - Zhang, Shenggui

AU - Li, Xueliang

AU - Wang, Ligong

PY - 2000

Y1 - 2000

N2 - 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)\mid d(x,y)=2\}\geq c/2$; 2. $w(xz)=w(yz)$ for every vertex $z\in N(x)\cap 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.

AB - 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)\mid d(x,y)=2\}\geq c/2$; 2. $w(xz)=w(yz)$ for every vertex $z\in N(x)\cap 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.

KW - MSC-05C45

KW - MSC-05C35

KW - MSC-05C38

M3 - Report

T3 - Memorandum Faculteit TW

BT - A fan type condition for heavy cycles in weighted graphs

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

Broersma H, Zhang S, Li X, Wang L. A fan type condition for heavy cycles in weighted graphs. Enschede: University of Twente, Department of Applied Mathematics, 2000. 13 p. (Memorandum Faculteit TW; 1513).