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
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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom