Connectivity of Inhomogeneous Random Graphs II

Abstract

Each graphon W:Ω2→[0,1]$$ W:{\Omega}^2\to \left[0,1\right] $$ yields an inhomogeneous random graph model 𝔾(n,W) . We show that 𝔾(n,W) is asymptotically almost surely connected if and only if (i) W$$ W $$ is a connected graphon and (ii) the measure of elements of Ω$$ \Omega $$ of W$$ W $$ ‐degree less than α$$ \alpha $$ is o(α)$$ o\left(\alpha \right) $$ as α→0$$ \alpha \to 0 $$ . These two conditions encapsulate the absence of several linear‐sized components, and of isolated vertices, respectively. We study in bigger detail the limit probability of the property that 𝔾(n,W) contains an isolated vertex, and, more generally, the limit distribution of the minimum degree of 𝔾(n,W) .