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
    @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