4
$\begingroup$

The Kirchhoff's theorem is a classical result for counting the number of spanning trees in a graph.

However, what are the best known upper bounds on the number of spanning trees in a graph in terms of structural parameters (e.g., number of vertices, degrees, etc.) instead of algebraic quantities?

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ You should tell in what terms do you want to get the bounds. $\endgroup$
    – Łukasz Grabowski
    Commented Oct 21, 2010 at 18:32
  • 2
    $\begingroup$ To expand on Lukasz' comment: the upper bound is infinity, and the lower bound is zero. If the number of vertices is $n$, the upper bound is whatever you get for the complete graph, the lower bound is still zero. Maybe a good question would be, if you fix $c$, $0\lt c\lt1/2$, and ask about graphs with $n$ vertices and roughly $cn^2$ edges, what upper and lower bounds do you get as functions of $c$ and $n$. But we shouldn't have to write your question for you. $\endgroup$
    – Gerry Myerson
    Commented Oct 22, 2010 at 0:03
  • 1
    $\begingroup$ As a rough count, if you've got n vertices, you've got less than $n^{n-2}$ trees. :) $\endgroup$
    – Gwyn Whieldon
    Commented Oct 22, 2010 at 1:28

4 Answers 4

Reset to default
5
$\begingroup$

I had an email discussion with Russell Lyons a few years ago about maximizing the number of spanning trees among all graphs with a given number of vertices and edges. He had a simple argument for an upper bound of $(2e/v)^{v-1}$. There's an even simpler argument for an upper bound of $e\choose v-1$. Russell thought there was a good bound for regular graphs due to McKay.

As for lower bounds, if the graph is not connected, it has zero spanning trees, and even an $n$-vertex graph with just $n-1$ edges missing (compared to the complete graph) may not be connected. I suppose one could restrict to connected graphs and then ask for a minimum.

EDIT: Here are bibliographical details on two papers by McKay:

McKay, Brendan D., Spanning trees in regular graphs, European J. Combin. 4 (1983), no. 2, 149–160, MR 85d:05194.

McKay, Brendan D., Spanning trees in random regular graphs, Proceedings of the Third Caribbean Conference on Combinatorics and Computing (Bridgetown, 1981), pp. 139–143, Univ. West Indies, Cave Hill Campus, Barbados, 1981, MR 83g:05030.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ When $e$ is close to $v$, the bound $\binom{e}{v-1}$ is stronger. Are there any stronger upper bounds than this for the case when $e$ is small? $\endgroup$
    – David Harris
    Commented Aug 11, 2011 at 12:43
3
$\begingroup$

Thank you all for your kind answers. In my question I was specifically interested in bounds given in terms of readily available quantities like number of vertices, edges, max degree, etc. Thanks to Gerry for his references. I have also learn about other references on my own. Essentially there is a good list of bounds in

L. Feng, et al., Sharp upper bounds for the number of spanning trees of a graph, Appl. Anal. Discrete Math. 2 (2008), 255-259.

Improve this answer
$\endgroup$
3
$\begingroup$

Kostochka's Upper Bound. It is now almost seven years that no one has mentioned the following widely-known, proved, completely general upper bound in terms of the degree-sequence:

Theorem (A. Kostochka) . Every finite graph $G$ has $\leq\frac{1}{\lvert G\rvert-1}\prod_{V\in V}\mathrm{d}_G(v)$ spanning trees.

Here, 'graph'='irreflexive symmetric binary relation on a set', and $\mathrm{d}_G(v)=\lvert\{e\in E(G)\colon v\in e\}\rvert$ denotes the vertex-degree. Needless to say,

this bound is sharp in the sense that there is an infinite family of graphs for which the bound holds with equality: the stars $K^{1,\lvert G\rvert-1}$, which are themselves trees.

Restricted to the class of all trees, the stars are of course the only graphs for which Kostochka's bound is sharp.

I find it a plausible

  • conjecture that stars are the only graphs for which Kostochka's bound is attained, but I do not know whether this is proved.

A proof of the above theorem of Kostochka was published in

A. V. Kostochka: The Number of Spanning Trees in Graphs with a Given Degree Sequence Random Structures and Algorithms 6(2-3) 1995

Improve this answer
$\endgroup$
0
$\begingroup$

kirchhoff's theorem gives both a lower and upper bound

Improve this answer
$\endgroup$
2
  • $\begingroup$ Link to statement and discussion of Kirchhoff's Matrix-Tree Theorem: en.wikipedia.org/wiki/Kirchhoff's_theorem $\endgroup$
    – Gerry Myerson
    Commented Oct 22, 2010 at 0:06
  • $\begingroup$ This answer is misleading: it is not logically wrong of course (since Kirchhoff's theorem gives an exact expression, either in terms of eigenvalues of the Laplacian or in terms of cofactors of the Laplacian, and of course an exact expression is simultaneously an upper bound and a lower bound), but it is misleadingly stated. Of course, one can sometimes derive lower and upper bounds from e.g. the eigenvalue version of Kirchhoff's theorem, by using eigenvalue estimates, but usually Kirchhoff's theorem is not seen as an estimate, rather as an exact algebraic result. $\endgroup$
    – Peter Heinig
    Commented Oct 16, 2017 at 13:54

You must log in to answer this question.