<p>Working on network design this summer I have come across certain applications that have inspired me to ask the following question:</p>

<p><em>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.?</em></p>

<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 <strong>enough</strong> vertices to end up with a connected induced subgraph.</p>

<p>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.</p>

<p>I am assuming the answer would be a function of some structural property(/ies) of the graph, like connectedness, minimum degree, expansion, etc.. </p>

CC BY-SA 3.0
2015-07-14T19:22:20.267Z
I guess high minimum degree isn't enough: Start with a few separate, large cliques; then connect all these vertices to a single central vertex. Now we must sample that central vertex in order to ensure connectivity w.h.p.
usul
CC BY-SA 3.0
2015-07-14T19:55:10.653Z
Yep, exactly. It can't be just that. Whenever the min cut is small you'd have problems like that.
Konstantinos Koiliaris
<reference-request><graph-theory><randomness>
Random Sampling Threshold to Get a Connected Induced Subgraph
Konstantinos Koiliaris
# Random Sampling Threshold to Get a Connected Induced Subgraph

(Asked by: username_0 on 2015-07-14)

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..

**Tags:** reference-request, graph-theory, randomness
> **Comments:**
> **username_1**: I guess high minimum degree isn't enough: Start with a few separate, large cliques; then connect all these vertices to a single central vertex. Now we must sample that central vertex in order to ensure connectivity w.h.p.  
> **username_0**: Yep, exactly. It can't be just that. Whenever the min cut is small you'd have problems like that.  

---

## 0 answers

