Let $G=(V,E)$ be a random Erdős-Renyi Graph, i.e., $G\in\mathcal{G}(n,p)$. It is well known that if $p=(\log n +c +o(1))/n$ with $c\in\Re$ then $$ P(G \text{ is connected})=e^{-e^{-c}}\ . $$

However, I found no information about the expectation of the diameter if $G$ is connected.

My question is: Let $G\in\mathcal{G}(n,p)$ with $p=(\log n +c +o(1))/n$ and $c\in\Re$. What is the value of $$ \mathbb{E}(diam\ G \mid G\text{ is connected}) $$

Is the result known? Or is it an open question? Any reference is welcome.


I'm performing simulations of several algorithms to compute the diameter of random graphs. Some of them are generated using the value of $p$ above. A graph is used only if it is connected. I would like to compare the results with the theoretical expectation.

  • $\begingroup$ Setting $c=1$, it appears numerically that $\mathbb{E}(\operatorname{diam} G | G \text{ is connected}) \leq \log n$ for large enough $n$ in an experiment I just ran. (Indeed, it appears to grow much slower than this.) $\endgroup$
    – cdipaolo
    Jun 25 '19 at 6:13
  • 1
    $\begingroup$ @cdipaolo Yes, I performed simulations with different values of $c$ and it seems that it is bounded by $O(\log n)$. I'm interested in a theoretical formula. $\endgroup$
    – Lamine
    Jun 25 '19 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.