A $\sigma_3$ type condition for heavy cycles in weighted graphs

Haitze J. Broersma, S. Zhang, X. Li, Xueliang Li

Research output: Book/ReportReportProfessional

17 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. The weighted degree sum of any three independent vertices is at least $m$; 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 $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 languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages12
Publication statusPublished - 2000

Publication series

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

Keywords

  • MSC-05C35
  • MSC-05C38
  • EWI-3334
  • METIS-141192
  • IR-65702
  • MSC-05C45

Cite this

Broersma, H. J., Zhang, S., Li, X., & Li, X. (2000). A $\sigma_3$ type condition for heavy cycles in weighted graphs. (Memorandum Faculteit TW; No. 1514). Enschede: University of Twente, Department of Applied Mathematics.
Broersma, Haitze J. ; Zhang, S. ; Li, X. ; Li, Xueliang. / A $\sigma_3$ type condition for heavy cycles in weighted graphs. Enschede : University of Twente, Department of Applied Mathematics, 2000. 12 p. (Memorandum Faculteit TW; 1514).
@book{37bb88512d8c43d4941ada9f3974c9db,
title = "A $\sigma_3$ 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. The weighted degree sum of any three independent vertices is at least $m$; 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 $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$.",
keywords = "MSC-05C35, MSC-05C38, EWI-3334, METIS-141192, IR-65702, MSC-05C45",
author = "Broersma, {Haitze J.} and S. Zhang and X. Li and Xueliang Li",
note = "Imported from MEMORANDA",
year = "2000",
language = "Undefined",
series = "Memorandum Faculteit TW",
publisher = "University of Twente, Department of Applied Mathematics",
number = "1514",

}

Broersma, HJ, Zhang, S, Li, X & Li, X 2000, A $\sigma_3$ type condition for heavy cycles in weighted graphs. Memorandum Faculteit TW, no. 1514, University of Twente, Department of Applied Mathematics, Enschede.

A $\sigma_3$ type condition for heavy cycles in weighted graphs. / Broersma, Haitze J.; Zhang, S.; Li, X.; Li, Xueliang.

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

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - A $\sigma_3$ type condition for heavy cycles in weighted graphs

AU - Broersma, Haitze J.

AU - Zhang, S.

AU - Li, X.

AU - Li, Xueliang

N1 - Imported from MEMORANDA

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. The weighted degree sum of any three independent vertices is at least $m$; 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 $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$.

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. The weighted degree sum of any three independent vertices is at least $m$; 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 $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$.

KW - MSC-05C35

KW - MSC-05C38

KW - EWI-3334

KW - METIS-141192

KW - IR-65702

KW - MSC-05C45

M3 - Report

T3 - Memorandum Faculteit TW

BT - A $\sigma_3$ type condition for heavy cycles in weighted graphs

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

Broersma HJ, Zhang S, Li X, Li X. A $\sigma_3$ type condition for heavy cycles in weighted graphs. Enschede: University of Twente, Department of Applied Mathematics, 2000. 12 p. (Memorandum Faculteit TW; 1514).