Suppose I have a connected graph with $n$ vertices and $n−1$ edges, that is in form of a tree. Now, I will add the number of vertices in the tree and uniformly randomly select a vertex. I break the graph at this selected vertex, deleting the vertex and the edges connected to it. Now, I again repeat the same thing at all of the left components (sub-trees) until I am left with one vertex for which the answer is inherently $1$. What will be the expectation of the sum obtained by adding the number of vertices recursively in such a problem?

For example, I have 3 vertices, A, B and C in which A is connected to B as well as C, but B and C are not connected. Like, B--A--C. Now, I could select any one vertex out of three with probability 1/3, so I add 3. Now, if I had selected A, I would repeat this for B and C separately adding one for each case. Otherwise, selecting B or C, I would have repeated it on A--C or B--A respectively, adding 2 and selecting each node again with probability 1/2.

I agree the problem is weakly written, here is a formulation suggested by Karolis Juodelė: I'm looking for the expected value of $f(G) = \left|V_G\right| + \sum f(G_i)$ where $G_i$ are components remaining after removing a random vertex of $G$.

  • $\begingroup$ I'm sorry, I still don't understand. I suggest you edit the question to make it more precise. It would also help to add an example (like the one in your comment, but edit the question to include it). Make sure to state the desired answer (the expectation, which should be a number) and how you got it. Also, what is the context where you ran into this? And, can you explain how this connects to computer science? Finally, tell us what you've tried so far. Have you tried writing a recurrence relation? If so, what did you get? $\endgroup$ – D.W. Sep 10 '13 at 18:54
  • $\begingroup$ Your question as I understand by your comments seems to be nice one, but badly written, you can change it to pseudo-code, (Or I'll do it later), to make it more clear to others. $\endgroup$ – user742 Sep 11 '13 at 8:55
  • 1
    $\begingroup$ As I understand, you want to find an expected value over all random trees of $n$ vertices. Then you should also specify the distribution of random trees you're using - I don't think there is a single natural one. $\endgroup$ – Karolis Juodelė Sep 11 '13 at 10:49

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.