The diameter of Inhomogeneous random graphs

Nicolas Fraiman, Dieter Mitsche

Published 2015-10-29Version 1

In this paper we study the diameter of Inhomogeneous random graphs $G(n,\kappa,p)$ that are induced by irreducible kernels $\kappa$. The kernels we consider act on separable metric spaces and are almost everywhere continuous. We generalize results known for the Erd\H{o}s-R\'enyi model $G(n,p)$ for several ranges of $p$. We find upper and lower bounds for the diameter of $G(n,\kappa,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.