The Average Distance and the Diameter of Dense Random Regular Graphs

Abstract

Let $\mathrm{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 $|\mathrm{AD}(G_{n,d})-\mu|<\epsilon$ holds with high probability for any constant $\epsilon>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.