2024/09/24 by Nastaran Behrooznia, Torsten Mütze, Behrooznia, Nastaran +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Stochastic processes and statistical mechanics #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2409.15793
We prove that the spanning trees of any outerplanar triangulation G can be listed so that any two consecutive spanning trees differ in an exchange of two edges that share an end vertex. For outerplanar graphs G with faces of arbitrary lengths (not necessarily 3) we establish a similar result, with the condition that the two exchanged edges share an end vertex or lie on a common face. These listings of spanning trees are obtained from a simple greedy algorithm that can be implemented efficiently, i.e., in time O(n log n) per generated spanning tree, where n is the number of vertices of G. Furthermore, the listings correspond to Hamilton paths on the 0/1-polytope that is obtained as the convex hull of the characteristic vectors of all spanning trees of G.