10
$\begingroup$

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.

Motivation:

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.

$\endgroup$
  • $\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 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 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.