### Abstract

A weighted graph is a graph in which each edge is assigned a non-negative number, called the weight. The weight of a path (cycle) is the sum of the weights of its edges. The weighted degree of a vertex is the sum of the weights of the edges incident with the vertex. A usual (unweighted) graph can be considered as a weighted graph with constant weight 1. In this paper, it is proved that for a 2-connected weighted graph, if every vertex has weighted degree at least d, then for any given vertex y, either y is contained in a cycle with weight at least 2d or every heaviest cycle is a Hamilton cycle. This result is a common generalization of Grötschel's theorem and Bondy–Fan's theorem assuring the existence of a cycle with weight at least 2d on the same condition. Also, as a tool for proving this result, we show a result concerning heavy paths joining two specific vertices and passing through one given vertex.

Original language | English |
---|---|

Pages (from-to) | 327-336 |

Number of pages | 10 |

Journal | Discrete mathematics |

Volume | 2000 |

Issue number | 223 |

DOIs | |

Publication status | Published - 2000 |

### Keywords

- Weighted degree
- Weighted graph
- optimal
- METIS-140662
- (Long
- IR-74275
- (Hamilton) cycle

## Fingerprint Dive into the research topics of 'Heavy paths and cycles in weighted graphs'. Together they form a unique fingerprint.

## Cite this

Zhang, S., Li, X., Li, X., & Broersma, H. J. (2000). Heavy paths and cycles in weighted graphs.

*Discrete mathematics*,*2000*(223), 327-336. https://doi.org/10.1016/S0012-365X(99)00413-6