ISSN:
1439-6912
Schlagwort(e):
05 B 35
;
05 c 20
;
68 Q 20
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Mathematik
Notizen:
Abstract LetG be a 2-connected rooted graph of rankr andA, B two (rooted) spanning trees ofG We show that the maximum number of exchanges of leaves that can be required to transformA intoB isr 2−r+1 (r〉0). This answers a question by L. Lovász. There is a natural reformulation of this problem in the theory ofgreedoids, which asks for the maximum diameter of the basis graph of a 2-connected branching greedcid of rankr. Greedoids are finite accessible set systems satisfying the matroid exchange axiom. Their theory provides both language and conceptual framework for the proof. However, it is shown that for general 2-connected greedoids (not necessarily constructed from branchings in rooted graphs) the maximum diameter is 2r−1.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF02122803
Permalink