Abstract
| Original language | Undefined |
|---|---|
| Place of Publication | Enschede |
| Publisher | University of Twente, Department of Applied Mathematics |
| Number of pages | 12 |
| Publication status | Published - 2000 |
Publication series
| Name | Memorandum Faculteit TW |
|---|---|
| Publisher | University of Twente |
| No. | 1514 |
| ISSN (Print) | 0169-2690 |
Keywords
- MSC-05C35
- MSC-05C38
- EWI-3334
- METIS-141192
- IR-65702
- MSC-05C45
Cite this
}
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/Report › Report › Professional
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 -