2025/08/19 by Karamchedu, Mithra, Bang, Lucas
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2508.13480
In this paper, we investigate the problem of generating the spanning trees of a graph G up to the automorphisms or "symmetries" of G. After introducing and surveying this problem for general input graphs, we present algorithms that fully solve the case of series-parallel graphs, under two standard definitions. We first show how to generate the nonequivalent spanning trees of a oriented series-parallel graph G in output-linear time, where both terminals of G have been individually distinguished (i.e. applying an automorphism that exchanges the terminals produces a different series-parallel graph). Subsequently, we show how to adapt these oriented algorithms to the case of semioriented series-parallel graphs, where we still have a set of two distinguished terminals but neither has been designated as a source or sink. Finally, we discuss the case of unoriented series-parallel graphs, where no terminals have been distinguished and present a few observations and open questions relating to them. The algorithms we present generate the nonequivalent spanning trees of G but never explicitly compute the automorphism group of G, revealing how the recursive structure of G's automorphism group mirrors that of its spanning trees.