The Diameter of Sparse Random Graphs

DOI10.1017/S0963548310000325zbMath1261.05096arXiv0808.4067OpenAlexW3103572255MaRDI QIDQ4911116

Oliver Riordan, Nicholas C. Wormald

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/0808.4067

zbMATH Keywords

diameterbranching processrandom graph

Mathematics Subject Classification ID

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

Related Items (28)

On the Diameter of Hyperbolic Random Graphs ⋮ On the Diameter of Hyperbolic Random Graphs ⋮ The mean and variance of the distribution of shortest path lengths of random regular graphs ⋮ Distributed algorithms for random graphs ⋮ The diameter of the directed configuration model ⋮ Weak disorder asymptotics in the stochastic mean-field model of distance ⋮ Unnamed Item ⋮ The continuum limit of critical random graphs ⋮ Concentration of rainbow \(k\)-connectivity of a multiplex random graph ⋮ The average distance and the diameter of dense random regular graphs ⋮ Mixing time of near-critical random graphs ⋮ Geodesic cycles in random graphs ⋮ Diameters of random circulant graphs ⋮ Diameter of the Stochastic Mean-Field Model of Distance ⋮ Unnamed Item ⋮ Diameter in ultra‐small scale‐free random graphs ⋮ Transience and recurrence of random walks on percolation clusters in an ultrametric space ⋮ Random walks on the random graph ⋮ On the Diameters of Commuting Graphs Arising from Random Skew-Symmetric Matrices ⋮ Anatomy of the giant component: the strictly supercritical regime ⋮ Strong noise sensitivity and random graphs ⋮ Approximate lumpability for Markovian agent-based models using local symmetries ⋮ On the Spread of Random Graphs ⋮ The Mixing Time of the Newman-Watts Small-World Model ⋮ Diameter and stationary distribution of random \(r\)-out digraphs ⋮ Unnamed Item ⋮ The diameter of weighted random graphs ⋮ Expansion in supercritical random subgraphs of the hypercube and its consequences

Cites Work

• Unnamed Item
• Distance in random graphs with infinite mean degrees
• Critical random graphs: Diameter and mixing time
• Counting connected graphs inside-out
• The diameter of random regular graphs
• The diameter of a scale-free random graph
• Distances in random graphs with finite mean and infinite variance degrees
• Inequalities with applications to percolation and reliability
• The Diameter of a Cycle Plus a Random Matching
• Component behavior near the critical point of the random graph process
• Cycles in a random graph near the critical point
• The Average Distance in a Random Graph with Given Expected Degrees
• Proof of the Van den Berg–Kesten Conjecture
• The phase transition in inhomogeneous random graphs
• Distances in random graphs with finite variance degrees
• The diameter of sparse random graphs
• The average distances in random graphs with given expected degrees
• Branching Processes
• The diameter of sparse random graphs

This page was built for publication: The Diameter of Sparse Random Graphs