### 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 language | English |
---|---|

Place of Publication | Enschede |

Publisher | University of Twente, Department of Applied Mathematics |

Number of pages | 13 |

Publication status | Published - 2000 |

### Publication series

Name | Memorandum Faculteit TW |
---|---|

Publisher | University of Twente |

No. | 1513 |

ISSN (Print) | 0169-2690 |

### Keywords

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

## 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

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.