Heavy paths and cycles in weighted graphs (Q1587616): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Sheng Gui Zhang / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Xue Liang Li / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Hajo J. Broersma / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Norman F.Quimpo / rank | |||
Normal rank |
Revision as of 11:12, 13 February 2024
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