Maximum of k-th maximal spanning trees of a weighted graph (Q1092057)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Maximum of k-th maximal spanning trees of a weighted graph |
scientific article |
Statements
Maximum of k-th maximal spanning trees of a weighted graph (English)
0 references
1987
0 references
Let T be a maximum-weight spanning tree in a connected weighted graph G and let P be an arbitrary spanning tree of G. The author proves that there exists a bijection b from \(A\setminus P\) onto \(P\setminus A\) such that for any edge a in \(A\setminus P\), \(P\setminus b(a)\cup a\) is a spanning tree of G whose weight is greater than or equal to that of P. This result is applied to some problems about spanning trees in a weighted graph.
0 references
spanning trees
0 references
weighted graph
0 references