Random Structures & Algorithms

The diameter of inhomogeneous random graphs

Abstract

In this paper, we study the diameter of inhomogeneous random graphs $G\left(n,\mathrm{\kappa },p\right)$ that are induced by irreducible kernels $\mathrm{\kappa }$. 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\left(n,\mathrm{\kappa },p\right)$ in terms of the expansion factor and two explicit constants that depend on the behavior of the kernel over partitions of the metric space.

View all

View all