= Graph ball
{title2=$B_G(v,r)$}
The closed graph ball of radius $r\geq0$ centered at vertex $v$ is
$$
B_G(v,r)=\{u\in V(G):d_G(u,v)\leq r\},
$$
where $d_G$ is shortest-path <distance (graph theory)>. In an unweighted graph, distances count edges, so a noninteger radius gives the same set as its integer part. Vertices in other connected components have infinite distance and lie outside every finite-radius ball.
For the path $1-2-3-4-5$, $B_G(3,1)=\{2,3,4\}$ and $B_G(3,2)$ is the whole vertex set. The sphere at radius one contains only $\{2,4\}$; a ball also contains its center and all smaller distances.
A graph ball is first a vertex set. If one wants a graph on those vertices, the induced subgraph convention must be specified. Ball growth, such as how $|B_G(v,r)|$ changes with $r$, records large-scale connectivity beyond the immediate vertex degree.
Back to article page
