1
$\begingroup$

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.

Thanks!

$\endgroup$
1

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.