Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
You can compute the value for small $n$, then feed it to oeis.org In this case, oeis.org/search?q=spanning&language=english&go=Search finds many choices but one is what you want. –  Ross Millikan Feb 22 '12 at 5:23
2  
@Ross: How can it be a known sequence? It depends on the graph and the assigned weights. –  Brian M. Scott Feb 22 '12 at 5:43
    
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 en.wikipedia.org/wiki/Kirchhoff's_theorem, the section on "Explicit enumeration of spanning trees" looks something like what I'm suggesting. –  Gerry Myerson Feb 22 '12 at 5:51
    
@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!) –  Elden Elmanto Feb 22 '12 at 14:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.