The average distance and the diameter of dense random regular graphs

DOI10.37236/8705MaRDI QIDQ2200440zbMATH OpenOpenAlexFDO

Authors Nobutaka Shimizu

Publication date 21 September 2020

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.37236/8705

zbMATH Keywords

embedding theoremswitching method

Mathematics Subject Classification ID

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

Review text

Summary: Let \(\text{AD}(G_{n,d})\) be the average distance of \(G_{n,d} \), a random \(n\)-vertex \(d\)-regular graph. For \(d=(\beta+o(1))n^{\alpha}\) with two arbitrary constants \(\alpha\in(0,1)\) and \(\beta>0\), we prove that \(|\text{AD}(G_{n,d})-\mu|<\varepsilon\) holds with high probability for any constant \(\varepsilon>0\), where \(\mu\) is equal to \(\alpha^{-1}+\exp(-\beta^{1/\alpha})\) if \(\alpha^{-1}\in\mathbb{N}\) and to \(\lceil\alpha^{-1}\rceil\) otherwise. Consequently, we show that the diameter of the \(G_{n,d}\) is equal to \(\lfloor\alpha^{-1}\rfloor+1\) with high probability.

Recommendations

• The diameter of dense random regular graphs
• The diameter of sparse random graphs
• The Average Distance in a Random Graph with Given Expected Degrees
• Random regular graphs of high degree
• The average distances in random graphs with given expected degrees

Cites work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Diameters of Random Graphs
• Distances in random graphs with finite variance degrees
• Embedding the Erdős-Rényi hypergraph into the random regular hypergraph and Hamiltonicity
• Generating random regular graphs
• Generating Random Regular Graphs Quickly
• scientific article; zbMATH DE number 3878974 (Why is no real title available?)
• scientific article; zbMATH DE number 3773632 (Why is no real title available?)
• scientific article; zbMATH DE number 1380601 (Why is no real title available?)
• Introduction to Random Graphs
• Maximum degree in graphs of diameter 2
• Moore graphs and beyond: a survey of the degree/diameter problem
• On Moore Graphs with Diameters 2 and 3
• Random graphs.
• Sandwiching random graphs: universality between random graph models
• Sandwiching random regular graphs between binomial random graphs
• Small subgraphs of random regular graphs
• The asymptotic number of labeled graphs with given degree sequences
• The Average Distance in a Random Graph with Given Expected Degrees
• The diameter of dense random regular graphs
• The Diameter of Random Graphs
• The diameter of random regular graphs
• The diameter of sparse random graphs
• The diameter of sparse random graphs
• The diameter of sparse random graphs
• Theory of evolutionary computation. Recent developments in discrete optimization
• Uniform generation of random regular graphs
• Uniform generation of random regular graphs of moderate degree
• Universality for distances in power-law random graphs

Cited in

(2)

• The diameter of dense random regular graphs
• The mean and variance of the distribution of shortest path lengths of random regular graphs

This page was built for publication: The average distance and the diameter of dense random regular graphs

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