Working on network design this summer I have come across certain applications that have inspired me to ask the following question:
Given an undirected connected graph $G=(V,E)$ what is the minimum number of vertices, $k$, sampled uniformly and independently at random from $V$ (without replacement), such that the induced subgraph on those vertices is connected w.h.p.?
Notice, I am not looking for a way to sample a connected (induced) subgraph, I am looking for a probabilistic guarantee that I have sampled enough vertices to end up with a connected induced subgraph.
Does this sounds familiar to anyone? A quick search was not very promising so I decided to ask here if anyone has any references or even directions to point me at.
I am assuming the answer would be a function of some structural property(/ies) of the graph, like connectedness, minimum degree, expansion, etc..