1
$\begingroup$

I hope I can avoid being confusing, but here goes.

I have a graph $(V, E)$, connected, undirected and with no loops. I also have an assignment of integer-valued weight to each edge of the graph. Note that this is the set up of the minimum spanning tree problem whose solution is well-know.

My question is: given an integer $n$, how many spanning trees are there of weight $n$? Is there a solution to compute this number? In other words, a function $f_{(V,E)}: \mathbb{N} \rightarrow \mathbb{N}$ that gives the number of spanning trees of a given weight. Perhaps something like Kirchoff's matrix tree theorem which gives you the total number of spanning trees.

THANKS!

  • 0
    You can compute the value for small $n$, then feed it to http://oeis.org/ In this case, http://oeis.org/search?q=spanning&language=english&go=Search finds many choices but one is what you want.2012-02-22
  • 2
    @Ross: How can it be a known sequence? It depends on the graph and the assigned weights.2012-02-22
  • 0
    Maybe if you replace the $(i,j)$ element in the Kirchoff matrix with $x^w$ where $x$ is an indeterminate and $w$ is the weight of the edge joining $i$ and $j$ you'll get a polynomial where the coefficient of $x^n$ is the number of spanning trees of weight $n$? Or maybe not, but see http://en.wikipedia.org/wiki/Kirchhoff's_theorem, the section on "Explicit enumeration of spanning trees" looks something like what I'm suggesting.2012-02-22
  • 0
    @GerryMyerson - oh that does reasonable. Thanks! (Of course now I seek a proof of that statement - I will give it a try or hunt around for one!)2012-02-22

0 Answers 0