3
$\begingroup$

Given a weighted simple undirected connected graph $G = (V, E, w:E \to \mathbb{R})$, let $\tau(G)$ be the set of all its spanning trees. Is there an efficient algorithm to determine or estimate with high probability the number

$W = \sum_{\mathcal{T} \in \tau(G)} \sum_{e \in E(\mathcal{T})} w(e)$

without actually enumerating all the spanning trees? Are there asymptotic estimates on this number?

Improve this question
$\endgroup$
2
  • $\begingroup$ For each $e$, it suffices to count in how many spanning trees it pparticipates. For that, you merge endpoints of $e$ and find the number of spanning trees in the resulting graph. en.wikipedia.org/wiki/Kirchhoff%27s_theorem may work (as I understand from the proof outline, you should find the determinant of minor $M_{11}$ of the Laplacian) (note that you'll need a multigraph version). Maybe this answer can also be useful. $\endgroup$ – Dmitry Aug 26 '20 at 15:05
  • $\begingroup$ @Dmitry thanks! I will accept that as the answer if you post it. $\endgroup$ – abhi01nat Aug 28 '20 at 8:13

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.