Automated Counting of Spanning Trees for Several Infinite families of Graphs

Pablo Blanco, Doron Zeilberger · 2025

Read Automated Counting of Spanning Trees for Several Infinite families of Graphs by Pablo Blanco, Doron Zeilberger (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-2507-03841.txt.

Description

Pablo Blanco and Doron Zeilberger automate the counting of spanning trees in endless graph families, in this 2025 paper. A spanning tree touches every point of a graph with no loops. For families like powers of cycles and paths, the counts follow a pattern captured by a rational formula.

Theory guarantees a finite machine behind the pattern, but finding it by hand is tedious. The authors instead compute many counts numerically with a classic determinant theorem, then fit the data to the formula. The fit can be certified afterward, keeping the result rigorous. Torus and grid graphs get a brief treatment. The method turns weeks of algebra into fast computation.

Catalog record

CREATORPablo Blanco, Doron Zeilberger
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE30 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-03841

Browse the full library · About the Tower of Babel