0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\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
    Commented Jun 15, 2015 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
    Commented Jun 15, 2015 at 15:13

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .