# Probability there is no vertex at distance larger than $d$ away from source in random graph?

Given a random (undirected and unweighted) graph $G$ on $n$ vertices where each of the edges has equal and independent probability $p$ of existing (see Erdős–Rényi model). Fix some vertex $u\in G$ and call it the source. I am interested in the probability that there is no vertex (in the whole graph) at a distance larger than $d$ away from the source.

Distance $d$ between $u\in G$ and $v\in G$ is measured by the number of edges between $u$ and $v$ along a shortest path.

Obviously, we assume that $d$ is finite. First, we must establish a generating function for $G(n,p)$. The probability that a vertex $v$ has degree $k$ is $p_k = \dbinom{n-1}kp^k(1-p)^{n-1-k}$ from the argument that we need to pick $k$ from $n-1$ and each of those have to be existing edges while the other edges should not exist.

Now we can approximate this binomial distribution by a Poission distribution for large $n$ with $p_k \approx e^{-c}\frac{c^k}{k!}$ where $c = p(n-1)$ or your expected number of neighbours.

Now that we have a generating function for a degree distribution, we can proceed as follows. Let $g_0(z) = \sum_{k = 0}^{\infty} p_kz^k$. This problem reduces to finding the degree distribution of a $d+1$th neighbor of a chosen vertex $v$ with degree $k$ in $G$.

It turns out that the degree distribution of the neighbour of vertex $v$ is $g_1(z) = \frac{g_0'(z)}{g_0'(1)}$. Furthermore, we can also prove that the degree distribution of $2$nd neighbors is $g_0(g_1(z))$ and it turns out that the degree distribution of the $d+1$th neighbour is $g_{d+1}(z) = g_{d}(g_{d-1}( \cdots g_1(g_0(z)) \cdots ))$.

Then we want the expected number of $d+1$th neighbors to be less than $1$. This value is just $g_{d+1}'(1)$.

• Hey, did you mean $g^{(d+1)}=g_0(g_1(\ldots (g_1(z))\ldots))$ instead? May 9 '14 at 1:52
• For anyone else who stumbles across: the answer given above is better explained in the following paper: arxiv.org/pdf/cond-mat/0007235v2.pdf. Thanks. May 9 '14 at 1:53
• If the edge probability $p$ is large enough, then the degree of a generic vertex is not well approximated by a Poisson distribution. Poisson approximation works when $np=c,$ where $c$ is a constant (which was the range looked at in that paper). However, in this range, the probability that $G(n,p)$ is connected is exponentially small. May 13 '14 at 14:09
• Actually, @Sandeep, $g_{d+1}^{'}(1)$ doesn't make sense. If $g_{d+1}(z)$ is the degree distribution of $d+1$th neighbors, then $g_{d+1}^{'}(1)$ is $\Sigma_{k=0}^{\infty}k p_k z^{k-1}$ which is not a probability, but the average number of $d+1$th neighbors. What am I missing? Aug 6 '14 at 17:24