Diameter of directed Erdős–Rényi graph

189 Views Asked by At

Let $G_{N, p} = (V, E)$ be a directed Erdős–Rényi graph. More specifically, $G_{N, p}$ is such that $|V| = N$ and, for all $i, j \neq i \in V$, the probability that $(i, j) \in E$ is $p$.

In this paper, Theorem 5 proves that $G_{N, p}$ is strongly connected with high probability as long as (somewhat unsurprisingly) $p > \log N / N$.

Now, I am wondering if any result exists on the diameter of $G_{N, p}$. Given the similarity between the connectivity thresholds of directed and undirected Erdős–Rényi graphs, one could think that diameters should be similar, too. However, I did not find any result about the topic.