RUS  ENG
Full version
SEMINARS



The number of spanning trees in a graph

D. D. Cherkashin

Institute of Mathematics and Informatics, Bulgarian Academy of Sciences

Abstract: The subject of the talk lies at the intersection of combinatorics, linear algebra and complex analysis.
Calculating the number of spanning trees in a graph goes back to the celebrated result of Kirchhoff (1847), who connected the number of trees and the Laplacian matrix. However, as was shown by Cayley (1889), there is a bijection between the summands of $(x_1 + x_2 + ... + x_n)^{(n-2)}$ and the trees in a complete $n$-vertex graph (and in particular the number of trees is $n^{(n-2)}$). Here a tree $T$ corresponds to a monomial in which degree of $x_i$ is equal to the degree of vertex $i$ in $T$ minus $1$. In other words the vertex spanning enumerator polynomial of a complete graph has a linear factorization. We discuss all strengthening of these results that I know, in particular the following result by C., Petrov and Prozorov (2023).
The following statements are equivalent.
1) A graph $G$ is distance-hereditary (i.e. every induced connected graph preserves distances).
2) The vertex spanning enumerator polynomial of $G$ factors into linear terms.
3) The vertex spanning enumerator polynomial of $G$ is real stable (i.e., it does not vanish when substituting any variables from the open upper complex half-plane).
We finish with open questions.

Language: English


© Steklov Math. Inst. of RAS, 2025