The diameter of inhomogeneous random graphs. Issue 2 (16th May 2018) - Fraiman, Nicolas; Mitsche, Dieter
Abstract: 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.