The average distance and the diameter of dense random regular graphs (Q2200440)

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.