@article{352caae0d503477ebbf34872ac4aecde,
title = "Heavy cycles in weighted graphs",
abstract = "An (edge-)weighted graph is a graph in which each edge e is assigned a nonnegative real number w(e), called the weight of e. The weight of a cycle is the sum of the weights of its edges, and an optimal cycle is one of maximum weight. The weighted degree w(v) of a vertex v is the sum of the weights of the edges incident with v. The following weighted analogue (and generalization) of a well-known result by Dirac for unweighted graphs is due to Bondy and Fan. Let G be a 2-connected weighted graph such that w(v) ≥ r for every vertex v of G. Then either G contains a cycle of weight at least 2r or every optimal cycle of G is a Hamilton cycle. We prove the following weighted analogue of a generalization of Dirac's result that was first proved by P{\'o}sa. Let G be a 2-connected weighted graph such that w(u)+w(v) ≥ s for every pair of nonadjacent vertices u and v. Then G contains either a cycle of weight at least s or a Hamilton cycle. Examples show that the second conclusion cannot be replaced by the stronger second conclusion from the result of Bondy and Fan. However, we characterize a natural class of edge-weightings for which these two conclusions are equivalent, and show that such edge-weightings can be recognized in time linear in the number of edges.",
keywords = "IR-96373, Weighted graph, (long, optimal, Hamilton) cycle, (edge-, vertex-)weighting, Weighted degree",
author = "Bondy, {J. Adrian} and Broersma, {Hajo J.} and {van den Heuvel}, Jan and Veldman, {Henk Jan}",
year = "2002",
doi = "10.7151/dmgt.1154",
language = "English",
volume = "22",
pages = "7--15",
journal = "Discussiones mathematicae. Graph theory",
issn = "1234-3099",
publisher = "University of Zielona Gora",
number = "1",
}