patternMinor
Probability of k-connectedness for a random graph with given degree sequence
Viewed 0 times
randomdegreegraphconnectednesswithsequenceforprobabilitygiven
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#80555, answer score: 2
Revisions (0)
No revisions yet.