Number of k-MSTs in a graph

41 Views Asked by At

I am wondering if there exists a theorem similar to the Matrix-Tree theorem of Kirchhof for finding the number of k-MSTs (Minimum Spanning Trees connecting exactly $k$ vertices in a graph). I am particularly interested in Algebraic Graph Theory and formulae similar to that of Kirchhof relating this number to the properties of the matrices associated with the super-graph [partially] spanned by these k-spanning trees. If it helps, the specific case I am interested in only concerns a connectivity graph that has binary weights on its edges and so the adjacency matrix is in the form of $\mathbf{A}\subset\{0,1\}^{n\times n}$. It goes without saying that eventually, it would be interesting to enumerate the k-MSTs, but that would go beyond the fundamental question. Any hint will be greatly appreciated!