Heavy paths and cycles in weighted graphs (Q1587616)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Heavy paths and cycles in weighted graphs |
scientific article |
Statements
Heavy paths and cycles in weighted graphs (English)
0 references
27 August 2001
0 references
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.
0 references
weighted graph
0 references
heavy path
0 references
heavy cycle
0 references
Hamiltonian cycle
0 references