Heavy paths and cycles in weighted graphs (Q1587616): Difference between revisions

A weighted graph is one in which each edge is assigned a nonnegative number or ``weight.'' Bondy and Fan gave analogues for weighted graphs of results by Erdős and Gallai on long paths and by Dirac on long cycles. This paper provides analogues for weighted graphs of results by Enomoto on long paths, and by Grötschel on long cycles, which pass through a specified vertex. The Bondy-Fan theorems are thereby generalized. In particular, if \(G\) is a 2-connected weighted graph where for each vertex \(v\) the weights of adjacent edges add up to at least \(d\), then, for any vertex \(y\) of \(G\), either \(G\) contains a cycle through \(y\) of weight at least \(2d\) or every heaviest cycle is Hamiltonian.