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
    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

    Identifiers