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

<p>However, I found no information about the expectation of the diameter if <span class="math-container">$G$</span> is connected.</p>

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

<p>Is the result known? Or is it an open question? Any reference is welcome.</p>

<p><strong>Motivation:</strong></p>

<p>I'm performing simulations of several algorithms to compute the diameter of random graphs. Some of them are generated using the value of <span class="math-container">$p$</span> above. A graph is used only if it is connected. I would like to compare the results with the theoretical expectation.</p>

CC BY-SA 4.0
2019-06-25T06:13:28.383Z
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.)
cdipaolo
CC BY-SA 4.0
2019-06-25T14:10:00.497Z
@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.
Lamine
<random-graphs><diameter>
Diameter of "almost" always connected Erdős-Renyi graphs
Lamine
# Diameter of "almost" always connected Erdős-Renyi graphs

(Asked by: username_0 on 2019-05-30)

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.

**Tags:** random-graphs, diameter
> **Comments:**
> **username_1**: 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.)  
> **username_0**: @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.  

---

## 0 answers

