We know that for a unweighted graph the number $\tau(\mathcal{G})$ of unique spanning trees of $\mathcal{G}$ is $$\tau(\mathcal{G})=\det L_\mathcal{G}^{\{n-1\}},$$ where $L_\mathcal{G}^{\{n-1\}}$ is constructed by removing an arbitrary $i$th row and column of graph Laplacian $L_\mathcal{G}$.

Now, I am concerned the weighted graph.

For example, consider complete graph $n=3$ with weights $e_1 = w_1$, $e_2 = w_2$, $e_3 = w_3$. We know $$\det(L_g^{n-1} ) = w_1w_2+w_1w_3+w_2w_3.$$ And actually, we have these three kinds of spanning tree. (and it also tells us what kind of spanning tree.)

For example, consider tree graph $n=3$, i.e., $1-2-3$ with weight $e_1 = w_1$, $e_2 = w_2$. We know $$\det(L_g^{n-1} ) = w_1w_2.$$ And of course, we only have one spanning tree.

So conclusion from these examples:

  1. number of terms $=$ number of spanning trees
  2. each term tells the type of spanning tree

My question is that are both conclusions general for any connected, weighted, undirected and no self-loop graph?

Any related papers are also welcome. I know $\tau(\mathcal{G})$ is related to loop entropy of $\mathcal{G}$ from a few papers; however, I have not seen the version for weighted graphs. So also hope for related papers if they are closely related to my problems.



Your Answer

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

Browse other questions tagged or ask your own question.