{"ID":2880488,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.13480","arxiv_id":"2508.13480","title":"Generating the Spanning Trees of Series-Parallel Graphs up to Graph Automorphism","abstract":"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.","short_abstract":"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 f...","url_abs":"https://arxiv.org/abs/2508.13480","url_pdf":"https://arxiv.org/pdf/2508.13480v1","authors":"[\"Mithra Karamchedu\",\"Lucas Bang\"]","published":"2025-08-19T03:18:31Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}