Premium
The diameter of inhomogeneous random graphs
Author(s) -
Fraiman Nicolas,
Mitsche Dieter
Publication year - 2018
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.20781
Subject(s) - mathematics , metric space , separable space , metric (unit) , kernel (algebra) , space (punctuation) , combinatorics , random graph , constant (computer programming) , upper and lower bounds , discrete mathematics , mathematical analysis , graph , computer science , operations management , economics , programming language , operating system
In this paper, we study the diameter of inhomogeneous random graphs G ( n , κ , p ) that are induced by irreducible kernels κ . The kernels we consider act on separable metric spaces and are almost everywhere continuous. We generalize results known for the Erdős–Rényi model G ( n , p ) for several ranges of p . We find upper and lower bounds for the diameter of G ( n , κ , p ) in terms of the expansion factor and two explicit constants that depend on the behavior of the kernel over partitions of the metric space.