The Diameter of Sparse Random Graphs

DOI10.1017/S0963548310000325zbMath1261.05096arXiv0808.4067MaRDI 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

diameter; branching process; random graph

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

05C12: Distance in graphs

Related Items

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

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