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|.$

  1. 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 \\\ 12 & 739026332 & 83.7 \\\ \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?


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.

  • $\begingroup$ @IgorPak Thank you for your answer. The stuff you mention is quite interesting. I am quite slow and can't really grasp the gist of the supplied preprint - the expression for calculating $F_G$ looks a bit messy to me. Could you perhaps extend your answer and supply some more details, perhaps an example? Thank you. $\endgroup$ – Jernej Aug 4 '12 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.