# Heavy paths and cycles in weighted graphs

Zhang, Shenggui
and
Li, Xueliang
and
Broersma, Hajo
(2000)
*Heavy paths and cycles in weighted graphs.*
Discrete Mathematics, 223
(1-3).
pp. 327-336.
ISSN 0012-365X

PDF
Restricted to UT campus only : Request a copy 89kB |

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

Item Type: | Article |

Copyright: | © 2000 Elsevier |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

Link to this item: | http://purl.utwente.nl/publications/74275 |

Official URL: | http://dx.doi.org/10.1016/S0012-365X(99)00413-6 |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page

Metis ID: 140662