
doi: 10.1007/bf02122803
Let G be a 2-connected rooted graph of rank r and A,B two (rooted) spanning trees of G. We show that the maximum number of exchanges of leaves that can be required to transform A into B is \(r^ 2-r+1(r>0)\). This answers a question by L. Lovász. There is a natural reformulation of this problem in the theory of greeoids, which asks for the maximum diameter of the basis graph of a 2- connected branching greedoid of rank r. 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 \(2^ r-1\).
greeoids, matroid exchange axiom, Directed graphs (digraphs), tournaments, maximum diameter, 2- connected branching greedoid, 2-connected rooted graph, basis graph, Combinatorial aspects of matroids and geometric lattices, Algorithms in computer science, Paths and cycles
greeoids, matroid exchange axiom, Directed graphs (digraphs), tournaments, maximum diameter, 2- connected branching greedoid, 2-connected rooted graph, basis graph, Combinatorial aspects of matroids and geometric lattices, Algorithms in computer science, Paths and cycles
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
