Maximal class of simple graphs of order $n$ with mutually distinct numbers of spanning trees

2012-06-27T22:26:53Z

This problem in some ways related to this post.

Let $A_n$ be the set of all integers $x$ such that there exist a connected simple graph of order $n$ having precisely $x$ spanning trees. Study the growth rate of $|A_n|.$

The question was raised by J.Sedlacek in his paper entitled: On the number of spanning trees of finite graphs, Cas. Pro. Pest Mat., Vol. 94 (1969) 217-221.

Sedlacek was able to show that $|A_n| = \omega(n)$ and remarked that it is not known if $|A_n| = \omega(n^2).$

Following are some observations about $|A_n|.$

Clearly $|A_n| \leq n^{n-2}$ and $|A_n| \leq |A_{n+1}|$
- Playing with prime partitions a bit it is possible to show that
$$ |A_n| = \omega(\sqrt{n}e^{\frac{2\pi}{\sqrt{3}}\sqrt{n/\log{n}}}) $$
- The following table can be computed using sage+nauty:

$$\begin{array}{ccc} n & |A_n| & \frac{n^{n-2}}{|A_n|}\\ 1 & 1 & 1 \\ 2 & 1 & 1 \\ 3 & 2 & 1.5 \\ 4 & 5 & 3.2 \\ 5 & 16 & 7.8 \\ 6 & 65 & 19.9\\ 7 & 386 & 43.5\\ 8 & 3700 & 70.8 \\ 9 & 55784 & 85.7\\ 10 & 1134526 & 88.1 \\ 11 & 27053464 & 87.1 \\ \end{array} $$

The bound mentioned under 2. was obtained using a construction of graphs with cut vertices. Since almost all graphs are blocks it is (in a way) reasonable to ask

Question. Is there a construction (using blocks) that can improve bound 2.?

I believe that this should also be provable:

Conjecture. $|A_n| = \omega(k^n)$ for all $k \in \mathbb{N}.$

In case this turns out to be a hard problem I would at least like to extend table 3. further. I am currently computing $|A_n|$ by generating all connected graphs of order $n$ with at least $n$ edges, computing their spanning trees and count distinct such numbers. One optimization could be derived by using the fact that $A_n \subset A_{n+1}$ but this is just a minor thing. I therefore leave the following question for the end:

Question. How can we compute $|A_n|$ quickly?

Answer by Igor Pak for Maximal class of simple graphs of order $n$ with mutually distinct numbers of spanning trees

2012-06-28T00:02:52Z

I don't have an answer to your asymptotics question, but I do have an idea how to approach your problem. Consider a graph $\Gamma=\Gamma(G_1,\ldots,G_k,H)$, where $H$ is a simple graph on $k$ vertices, where $\Gamma$ is obtained by making $G_i$ to be "parts" and connecting every vertex in $G_i$ with every vertex in $G_j$ if $(i,j)\in H$. This construction generalizes a multipartite graphs and hopefully should give you a better asymptotics if you set up the induction right.

Define $F_G(z) = \sum_r f(G,r) z^r$, where $f(G,r)$ is the number of rooted spanning forests in $G$ with $r$ roots. This way $F_G(0)$ is $n$ times the number of spanning trees in $G$, and $F_G(1)$ is the number of spanning trees in $\widehat G$, defined as a vertex connected to all $v\in G$. Turns out, $F_\Gamma$ is a product of $F_{G_i}$ and $F_H$ with appropriate substitutions. See this really short note, and this preprint which explains it better.

Maximal class of simple graphs of order $n$ with mutually distinct numbers of spanning trees - MathOverflow

Maximal class of simple graphs of order $n$ with mutually distinct numbers of spanning trees

Answer by Igor Pak for Maximal class of simple graphs of order $n$ with mutually distinct numbers of spanning trees