ISSN:
1439-6912
Keywords:
05 B 35
;
05 c 20
;
68 Q 20
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02122803
Permalink
