Automated counting of spanning trees for several infinite families of graphs

Using the theoretical basis developed by Yao and Zeilberger, we consider certain graph families whose structure results in a rational generating function for sequences related to spanning tree enumeration.Said families are powers of cycles and powers of paths; later, we briey discuss toru graphs and grid graphs.In each case we know, a priori, that the set of spanning trees of the family of graphs can be described in terms of a nite-state-machine, and hence there is a nite transfer matrix that guarantees the generating function is rational.Finding this grammar, and hence the transfer matrix is very tedious, so a much more ecient approach is to use experimental mathematics.Since computing numerical determinants is so fast, one can use the matrix tree theorem to generate suciently many terms, then t the data to a rational function.The whole procedure can be done rigorously a posteriori.We also construct generating functions for the quantity total number of leaves over all spanning trees, and automatically derive the asymptotics for both number of spanning trees and the sum of the number of leaves, enabling our computer to get the asymptotic for the average number of leaves per vertex in a random spanning tree in each family that always tends to a certain number, which we compute explicitly.This number, which we christen the B-Z constant for the innite family, is always some (often complicated) algebraic number, in contrast to the family of complete graphs, where this constant is 1/e (a transcendental number).