# zbMATH — the first resource for mathematics

Asymptotic enumeration of spanning trees. (English) Zbl 1076.05007
“Methods of enumeration of spanning trees in a finite graph $$G$$ and relations to various areas of mathematics and physics have been investigated for more than 150 years.” The famous matrix-tree theorem (due originally to Kirchhoff) states that the number $$\tau(G)$$ of spanning trees of a finite graph $$G$$ is equal to any cofactor of the graph Laplacian matrix (the degree matrix of $$G$$ minus the adjacency matrix of $$G$$). Use of this theorem often leads to an asymptotic approximation of the form $\frac{\log\tau(G_n)}{ | \text{vertex\;set\;of\;} G_n| } \to C,$ for some constant $$C$$ expressible as an integral, as the cardinality of the vertex set goes to infinity. This paper gives an effective expression for $$C$$ for “finite connected graphs with bounded average degree whose random weak limit is a probability measure on infinite rooted graphs” (covering many known cases). The expression is essentially in terms of the so-called “tree entropy”, the logarithm of a normalized determinant of the graph Laplacian for infinite graphs, and has an additional numeric value. Different interpretations of the tree entropy are also given.

##### MSC:
 05A16 Asymptotic enumeration 05C30 Enumeration in graph theory 05C05 Trees 60C05 Combinatorial probability
##### Keywords:
matrix-tree theorem; random walks; uniform spanning forests
Full Text: