k-connectivity threshold for superpositions of Bernoulli random graphs

Abstract

Let $G_1,\dots ,G_m$ be independent identically distributed Bernoulli random subgraphs of the complete graph ${\mathcal{K}}_n$ having vertex sets of random sizes $X_1,\dots ,X_m\in \{0,1,2,\dots \}$ and random edge densities $Q_1,\dots ,Q_m\in [0,1]$. Assuming that each $G_i$ has a vertex of degree $1$ with positive probability, we establish the $k$-connectivity threshold as $n,m\to +\infty$ for the union ${\cup }_{i=1}^m{G}_i$ defined on the vertex set of ${\mathcal{K}}_n$.

21 pages