The diameter of inhomogeneous random graphs

DOI10.1002/RSA.20781MaRDI QIDQ4684831zbMATH OpenOpenAlexWikidataFDO

Authors Nicolas Fraiman, D. Mitsche

Publication date 25 September 2018

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.08882

zbMATH Keywords

concentration inequalitiesdiameterneighborhood expansionrandom graphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Random graphs (graph-theoretic aspects) (05C80)

Abstract: 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 ErdH{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.

Recommendations

• Connectivity of inhomogeneous random graphs
• The diameter of sparse random graphs
• The diameter of sparse random graphs
• Sparse graphs: metrics and random models
• On the diameter of a class of random graphs

Cited in

(7)

• Stretch and diameter in random geometric graphs
• Cliques in rank-1 random graphs: the role of inhomogeneity
• Connectivity of inhomogeneous random graphs
• An estimate of the probability of localisation of the diameter of a random scale-free graph
• On the diameter of a class of random graphs
• On distribution function of the diameter in uncertain graph
• A limit theorem for small cliques in inhomogeneous random graphs

This page was built for publication: The diameter of inhomogeneous random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4684831)