Premium
Connectivity of inhomogeneous random graphs
Author(s) -
Devroye Luc,
Fraiman Nicolas
Publication year - 2014
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20490
Subject(s) - struct , random graph , mathematics , separable space , combinatorics , vertex (graph theory) , random regular graph , metric space , discrete mathematics , graph , space (punctuation) , chordal graph , computer science , 1 planar graph , mathematical analysis , programming language , operating system
Abstract We find conditions for the connectivity of inhomogeneous random graphs with intermediate density. Our results generalize the classical result for G ( n, p ), when p = c log n / n . We draw n independent points X i from a general distribution on a separable metric space, and let their indices form the vertex set of a graph. An edge ( i, j ) is added with probability min ( 1 , κ ( X i , X j ) log n / n ) , where κ ≥ 0 is a fixed kernel. We show that, under reasonably weak assumptions, the connectivity threshold of the model can be determined. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 408‐420, 2014