On the strength of connectedness of unions of random graphs

Abstract

Let $G_1,\dots ,G_m$ be independent identically distributed random subgraphs of the complete graph ${\mathcal{K}}_n$. We analyse the threshold behaviour of the strength of connectedness of the union ${\cup }_{i=1}^m{G}_i$ defined on the vertex set of ${\mathcal{K}}_n$. Let $a=\min \{t\ge 1:\mathbf{P}\{\delta (G_1)=t>0\}\}$ be the minimal non zero vertex degree attained with positive probability. Given $k\ge 0$ let $\lambda (k)=\ln n+k\ln \frac{m}{n}-\frac{m}{n}\mathbf{E}X$, where $X$ stands for the number of non isolated vertices of $G_1$. Letting $n,m\to +\infty$ we show that $\mathbf{P}\{{\cup }_{i=1}^m{G}_i$ is $a(k+1)$-connected$\}\to 1$ for $\lambda (k)\to -\infty$, and $\mathbf{P}\{{\cup }_{i=1}^m{G}_i$ is $ak+1$-connected$\}\to 0$ for $\lambda (k)\to +\infty$. In particular, the connectivity strength of the union graph ${\cup }_{i=1}^m{G}_i$ increases in steps of size $a$. Our results are obtained in a more general setting where the contributing random subgraphs do not need to be identically distributed.

The paper provides proof of the results reported by the author at the 10th Cracow Conference on Graph Theory, 2025