Connectivity of inhomogeneous random graphs II

2023/05/05 by Jan Hladký, Gopal Viswanathan, G.B. Viswanathan +2
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Stochastic processes and statistical mechanics #math.CO

paper · pdf · doi:10.48550/arxiv.2305.03607

openalex publication_date 2023/05/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Related

• Connectivity of inhomogeneous random graphs
• The connectivity and phase transition in inhomogeneous random graphs of finite types
• On the Asymptotic Connectivity of Random Networks under the Random Connection Model
• Joint Vertex Degrees in an Inhomogeneous Random Graph Model
• Connectivity of Large Scale Networks: Distribution of Isolated Nodes