Let $G$ be an ER graph $G = G(n,p)$ which is constructed by connecting nodes randomly and each edge is included in the graph with probability $p$ independent from every other edge.
For every pair of vertices $(u,v)$, the distance $d(u,v)$ is the length of the shortest path from $u$ to $v$. Let $q(m) = \Pr[d(u,v) = m]$. What is known about $q(\cdot)$?
Indeed,
- $q(1) = p$ and $q(2) = (1-(1-p^2)^{n-2})(1-p)$
- $q(1)+ q(2) + \cdots + q(n) = 1$
I think there is not a closed form of $q(\cdot)$ perhaps. Is there an asymptotic formula of $q(\cdot)$?