Generating the Spanning Trees of Series-Parallel Graphs up to Graph Automorphism
Mithra Karamchedu, Lucas Bang · 2025
Read Generating the Spanning Trees of Series-Parallel Graphs up to Graph Automorphism by Mithra Karamchedu, Lucas Bang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-13480.txt.
Introduction
Mithra Karamchedu and Lucas Bang list a graph's spanning trees and count twin copies as one. For series-parallel graphs, they solve the task in full. Plain lists drown in twin copies from the graph's own shape flips. The paper scans the task for graphs at large, then builds tools for the two-end set.
Where each end is marked on its own, list time tracks list size. In the half-marked case, ends are a marked pair with no set roles, and the same tools bend to fit. The case with no marks at all is left to notes and open asks. One sharp point: the tools never work out the flip group as such. The loop shape of the twins' traits tracks the loop shape of the trees.
Catalog record
| CREATOR | Mithra Karamchedu, Lucas Bang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 99 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-13480
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Generating the Spanning Trees of Series-Parallel Graphs up to Graph Automorphism Thanks: Posted 08/18/2025. Mithra Karamchedu, Lucas Bang Abstract In this paper, we investigate the problem of generating the spanning trees of a graph G G up to the automorphisms or “symmetries” of G 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 G in output-linear time, where both terminals of G 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 G but never explicitly compute the automorphism group of G G , revealing how the recursive structure of G G ’s automorphism group mirrors that of its spanning trees. keywords graph automorphisms, graph algorithms, combinatorial graph theory Funding. This work was supported in part by National Science Foundation Grant No. 1950885, during the summer Mithra Karamchedu participated in a computer science REU program at Harvey Mudd College. † † runningheads: Spanning Trees of SP Graphs up to Automorphism / Mithra Karamchedu and Lucas Bang AMS 05C60, 05C85, 68R10 1 Introduction In this paper, we examine the algorithmic aspects of generating a graph’s spanning trees under the actions of graph automorphism. Specifically, given a input graph G , we ask whether we can efficiently generate the nonequivalent spanning trees of G up to G ’s automorphisms—where two spanning trees T_{1} and T_{2} are equivalent when T_{1}=\sigma T_{2} for some \sigma\in\text{Aut}(G) . In addition to surveying this problem over general input graphs, we present algorithms that solve the case of series-parallel graphs. Spanning tree algorithms are of fundamental importance in computer science and discrete mathematics, and numerous combinatorial problems related to counting and generating spanning trees have been extensively studied [ 2 , 7 , 14 ] . In this paper, we build upon existing problems by also considering how the spanning trees of a graph G relate to the symmetric structure of G , their ambient graph. Several researchers have explored questions closely related to those we study here. In their 1990 paper, Kano and Sakamoto prove necessary and sufficient criteria for a labeled, undirected graph G to have a spanning tree fixed by a subgroup of G ’s automorphisms [ 6 ] . In their respective 2008 and 2009 master’s theses, Mohr and Van den Boomen study the problem of generating the equivalence classes of G ’s spanning trees up to tree isomorphism —where the spanning trees T_{1} and T_{2} are equivalent when there exists an isomorphism \sigma such that T_{1}=\sigma T_{2} [ 11 , 18 ] . We take the same problem that Mohr and Van den Boomen examine but place the additional constraint that the isomorphism \sigma is also an automorphism of G . To illustrate this problem, let us consider the diamond graph D below: D\hskip 5.0pt=\hskip 5.0pt\hbox to103.73pt{\vbox to61.05pt{\pgfpicture\makeatletter\hbox{\hskip 9.18588pt\lower-30.52545pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {{\lx@inpgf@ignorespaces}} \lxSVG@begingroup@{_scopebegin} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{{}{{{}}}{{}}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{}{}{}{}{}{\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 12.16 0 C 12.16 6.71 6.71 12.16 0 12.16 C -6.71 12.16 -12.16 6.71 -12.16 0 C -12.16 -6.71 -6.71 -12.16 0 -12.16 C 6.71 -12.16 12.16 -6.71 12.16 0 Z M 0 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{60}\lxSVG@closescope }}} \lxSVG@closescope }}} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{{}{{{}}}{{}}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{}{}{}{}{}{\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 71.21 29.53 C 71.21 36.24 65.77 41.68 59.06 41.68 C 52.34 41.68 46.9 36.24 46.9 29.53 C 46.9 22.81 52.34 17.37 59.06 17.37 C 65.77 17.37 71.21 22.81 71.21 29.53 Z M 59.06 29.53}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{40.17914pt}{18.11736pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{60}\lxSVG@closescope }}} \lxSVG@closescope }}} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{{}{{{}}}{{}}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{}{}{}{}{}{\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 71.21 -29.53 C 71.21 -22.81 65.77 -17.37 59.06 -17.37 C 52.34 -17.37 46.9 -22.81 46.9 -29.53 C 46.9 -36.24 52.34 -41.68 59.06 -41.68 C 65.77 -41.68 71.21 -36.24 71.21 -29.53 Z M 59.06 -29.53}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{40.17914pt}{-24.56178pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{60}\lxSVG@closescope }}} \lxSVG@closescope }}} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{{}{{{}}}{{}}{}{}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{}{}{}{}{}{\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 130.27 0 C 130.27 6.71 124.82 12.16 118.11 12.16 C 111.4 12.16 105.95 6.71 105.95 0 C 105.95 -6.71 111.4 -12.16 118.11 -12.16 C 124.82 -12.16 130.27 -6.71 130.27 0 Z M 118.11 0}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{82.85828pt}{-3.22221pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{60}\lxSVG@closescope }}} \lxSVG@closescope }}} \lxSVG@closescope \par{{}}{}{{}} {{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 11.37 5.68 L 47.69 23.84}{fill:none} \lx@inpgf@ignorespaces {{}}{}{{}} {{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 11.37 -5.68 L 47.69 -23.84}{fill:none} \lx@inpgf@ignorespaces {{}}{}{{}} {{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 70.42 -23.84 L 106.74 -5.68}{fill:none} \lx@inpgf@ignorespaces {{}}{}{{}} {{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 59.05 16.82 L 59.05 -16.82}{fill:none} \lx@inpgf@ignorespaces {{}}{}{{}} {{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 70.42 23.84 L 106.74 5.68}{fill:none} \lx@inpgf@ignorespaces \lxSVG@closescope {{{}}{}{{}}{}}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\vskip 5.0pt We find that D has the following eight spanning trees: 1 2 3 4 T_{1} 1 2 3 4 T_{2} 1 2 3 4 T_{3} 1 2 3 4 T_{4} 1 2 3 4 T_{5} 1 2 3 4 T_{6} 1 2 3 4 T_{7} 1 2 3 4 T_{8} Furthermore, the automorphism group of D is given by \displaystyle\text{Aut}(D) \displaystyle=\Bigg\{\,\underbrace{\begin{pmatrix}1&2&3&4\\ 1&2&3&4\end{pmatrix}}_{e},\underbrace{\begin{pmatrix}1&2&3&4\\ 4&2&3&1\end{pmatrix}}_{h},\underbrace{\begin{pmatrix}1&2&3&4\\ 1&3&2&4\end{pmatrix}}_{v},\underbrace{\begin{pmatrix}1&2&3&4\\ 4&3&2&1\end{pmatrix}}_{r}\,\Bigg\}, where e is the identity, h is the horizontal flip, v is the vertical flip, and r=hv is the 180^{\circ} rotation. With this, we can generate the orbits of \textsf{ST}(D) over \text{Aut}(D) , the sets of mutually equivalent spanning trees. In particular, we have that T_{1}=vT_{2}=rT_{3}=hT_{4},\qquad T_{5}=rT_{6},\qquad T_{7}=vT_{8}, so our three orbits of equivalent trees are \{T_{1},T_{2},T_{3},T_{4}\} , \{T_{5},T_{6}\} , and \{T_{7},T_{8}\} . Intuitively speaking, the three orbits represent the three fundamentally different “kinds” of spanning trees that D has up to its symmetric structure: the first orbit represents paths that circle the outside of D , the second represents paths that use the central edge of D , and the third represents so-called “claw” graphs (with three leaves that hinge on a central vertex). The problem of generating the spanning trees of a graph G up to automorphism is the same as returning exactly one representative from each orbit. We can therefore say that the nonequivalent spanning trees of D are, for instance, T_{1} , T_{5} , and T_{7} (among the several ways to choose orbit representatives). Visually, these nonequivalent spanning trees are: 1 2 3 4 T_{1} 1 2 3 4 T_{5} 1 2 3 4 T_{7} 1.1 Summary of Paper In Section 2 below, we introduce the prerequisite concepts and notation that will be used throughout the paper. In Section 3 , we then analyze the complexity of a brute-force algorithm (Algorithm 1 ) that solves this problem, and we briefly discuss special cases in which we can substantially improve upon Algorithm 1 . In Section 4 , we formally define series-parallel graphs and what makes such a graph “oriented,” “semioriented,” or “unoriented.” In Section 5 , we fully solve the case of oriented series-parallel graphs and analyze the complexity of the algorithms we propose for them. We then explore semioriented graphs in Section 6 , showing how they largely reduce the oriented case with a few lexicographical modifications.