Consider the $G(n,p)$ random graph model where $n$ is a ``large'' positive integer and $p\in (0,1)$. We may equip every realized random graph $G$ with its shortest path distance, making it into a (random) metric space $(G,d\_G)$. Since $G$ is finite then $(G,d\_G)$ is [doubling](https://en.wikipedia.org/wiki/Doubling_space).


Are there known estimates for the expected doubling constant of such a random graph?



Expected doubling constant of a random Erdős–Rényi graph
Let me assume $p > (1 + \varepsilon)(2 \ln n/ n)^{1/2}$, this in particular includes the case of constant $p \in (0,1)$.


If $p > (1 + \varepsilon)(2 \ln n/ n)^{1/2}$ then w.h.p. the binomial random graph $G(n,p)$ has diameter at most $2$. Also, for $p = \omega( \ln n / n)$ then w.h.p. every vertex has degree $(1 \pm o(1)) p n$. Thus the balls centered at any vertex have size $1$, $(1 \pm o(1)) p n$, and $n$; if the radius of the ball is $0, 1$ or at least $2$ respectively.


It seems that the only cases to consider are: how many singletons are needed to cover a radius-$1$ ball; and how many radius-$1$ balls are needed to cover the whole vertex set. In the first case any radius-$1$ ball trivially needs $(1 \pm o(1))pn$ singletons to cover it.


In the second case we are equivalently asking for the size of a minimum *dominating set* in $G(n,p)$, i.e. the minimum size of a set $S \subseteq V(G)$ where every vertex not in $S$ has a neighbour in $S$. This is known (see, e.g. [*Wieland, Ben; Godbole, Anant P.*, [**On the domination number of a random graph**](http://www.emis.de/journals/EJC/Volume_8/Abstracts/v8i1r37.html), Electron. J. Comb. 8, No. 1, Research paper R37, 13 p. (2001). [ZBL0989.05108](https://zbmath.org/?q=an:0989.05108).]) to be, w.h.p., concentrated around $(1 + o(1))\log\_q(n)$, where $q = 1/(1-p)$.


Then the doubling constant will depend on which of $(1 + o(1))\log\_q(n)$ or $(1 + o(1))pn$ is maximum. For constant $p \in (0,1)$ the former term is logarithmic and the second one is linear, so the doubling constant is $(1 + o(1))pn$.


