Diameters in Supercritical Random Graphs Via First Passage Percolation

DOI10.1017/S0963548310000301zbMath1260.05048arXiv0906.1840OpenAlexW1981896702MaRDI QIDQ4911110

Yuval Peres, Jeong Han Kim, Jian Ding, Eyal Lubetzky

Publication date: 13 March 2013

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

diameterErdős-Rényi random graphsupercritical giant component

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Distance in graphs (05C12)

Related Items

On the Cover Time of the Emerging Giant, The continuum limit of critical random graphs, Mixing time of near-critical random graphs, Diameters of random circulant graphs, Diameter of the Stochastic Mean-Field Model of Distance, First passage percolation on random graphs with finite mean degrees, The Evolution of the Cover Time, Upper Deviations for Split Times of Branching Processes, Aggregation models with limited choice and the multiplicative coalescent, Anatomy of the giant component: the strictly supercritical regime, First passage percolation on sparse random graphs with boundary weights, Anatomy of a young giant component in the random graph, On the Spread of Random Graphs, Joint Distribution of Distances in Large Random Regular Networks, The diameter of weighted random graphs

Cites Work

• Critical random graphs: Diameter and mixing time
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Random walks, capacity and percolation on trees
• First passage percolation on random graphs with finite mean degrees
• Component behavior near the critical point of the random graph process
• The phase transition in inhomogeneous random graphs
• The diameter of sparse random graphs
• The diameter of sparse random graphs
• Unnamed Item