3
$\begingroup$

For a degree sequence $(d_1,\ldots, d_n)$ with $\min d_i \geq k$ pick a graph with that degree sequence uniformly at random. What's the probability that the graph is k-connected?

I know that for Erdos-Renyi graphs the k-connectivity threshold coincides with with the appearance of degree k vertices, but that doesn't say much about the probability when we only know that the minimum degree is $k$.

This question is related to this question. I'd like to estimate how many graphs you need to sample before picking a biconnected graph.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The answer probably mildly depends on how wild the $d_i$ are. A random $k$-regular graph is $k$-connected whp for $3 \leq k \leq n-4$ according to slides by Wormald (page 12), so I would expect that if, say, $k \leq d_i \leq \ell$ for constants $k,\ell$ (or even $\ell$ growing mildly with $n$) then the graph is still $k$-connected whp. The proof shouldn't be difficult (for constant $\ell$) using the configuration model.

A 1-regular graph is never connected (for $n > 2$), and a random 2-regular graph is, if I remember correctly, disconnected whp. If you only have a few degree 2 vertices then perhaps the graph is 2-connected whp – that would be my guess.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.