The average distance and the diameter of dense random regular graphs

Nobutaka Shimizu¹

¹The University of Tokyo

The electronic journal of combinatorics, Tome 27 (2020) no. 3

Résumé

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.

Détail

DOI : 10.37236/8705

Classification : 05C80, 05C12
Mots-clés : switching method, embedding theorem