HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Probability of k-connectedness for a random graph with given degree sequence

Submitted by: @import:stackexchange-cs··
0
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.

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.

Context

StackExchange Computer Science Q#80555, answer score: 2

Revisions (0)

No revisions yet.