Connectivity of Inhomogeneous Random Graphs II

Abstract

Each graphon 𝑊:Ω² →[0,1] yields an inhomogeneous random graph model 𝔾⁡(𝑛,𝑊). We show that 𝔾⁡(𝑛,𝑊) is asymptotically almost surely connected if and only if (i) 𝑊 is a connected graphon and (ii) the measure of elements of Ω of 𝑊-degree less than 𝛼 is 𝑜⁡(𝛼) as 𝛼 →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 𝔾⁡(𝑛,𝑊) contains an isolated vertex, and, more generally, the limit distribution of the minimum degree of 𝔾⁡(𝑛,𝑊).