Heavy paths and cycles in weighted graphs (Q1587616): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
(2 intermediate revisions by one other user not shown) | |||
Property / author | |||
Property / author: Sheng Gui Zhang / rank | |||
Property / author | |||
Property / author: Xue Liang Li / rank | |||
Property / author | |||
Property / author: Hajo J. Broersma / rank | |||
Property / reviewed by | |||
Property / reviewed by: Norman F.Quimpo / rank | |||
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 | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Latest revision as of 05:00, 5 March 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