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

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