For a simple, finite, connected and complete graph $K_n = (V(K_n), E(K_n))$ with vertex set $V(K_n)$ and edge set $E(K_n)$, we assign a non-negative independent and identical distributed random weight $\xi_e$ with distribution $F$ to each edge $e \in E(K_n)$. We also assign a probability of appearance $0\le P_v \le 1$ to each $v \in V(K_n)$ as well. Then what is the expected lengths of the minimum spanning trees?

In case of no probability on the vertices this problem was solved by Wenbo Li and Xinyi Zhang in 2008.

  • $\begingroup$ Don't you just get a weighted average of the values on smaller sets of vertices, weighted by the probability that many vertices appear? $\endgroup$ – Douglas Zare Jun 15 '15 at 5:46
  • $\begingroup$ I am not sure about the weighted average because Steele in 2002 suggests to take into account the Tutte polynomial of the graph as well. In this case we have a sequence of weighted complete graphs that might have smaller vertex set in some points. $\endgroup$ – Sam Jun 15 '15 at 15: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.