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?

$\endgroup$
  • 5
    $\begingroup$ You should tell in what terms do you want to get the bounds. $\endgroup$ – Łukasz Grabowski Oct 21 '10 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 Oct 22 '10 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 Oct 22 '10 at 1:28
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.

$\endgroup$
  • 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 Aug 11 '11 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.

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

$\endgroup$
0
$\begingroup$

kirchhoff's theorem gives both a lower and upper bound

$\endgroup$
  • $\begingroup$ Link to statement and discussion of Kirchhoff's Matrix-Tree Theorem: en.wikipedia.org/wiki/Kirchhoff's_theorem $\endgroup$ – Gerry Myerson Oct 22 '10 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 Oct 16 '17 at 13:54

Your Answer

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