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$
2
  • $\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
    Commented Jun 25, 2019 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
    Commented Jun 25, 2019 at 14:10

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.