2
$\begingroup$

I am trying to understand what that sentence means. Intuitively, its obvious a radius ball means in a $ \mathbb{R}^{n}$ with respect to some norm. Its just the following set:

$$ B(v, r) = \{ x \in \mathbb{R}^n : \| v - x\| \leq r\}$$

i.e. its just all the points that are distance $ \| v - x\|^2 $ away from the center with respect to some norm $ \| \cdot\|$. However, in graph theory, if we have a graph $G = (V,E)$ I seem to have a much harder time to rigorously understand what this set means. Can someone help me define this set rigorously so that there is no doubt in my mind what it means to have a radius ball with at most radius $r$ in a fixed known graph $G = (V,E)$? In particular this is the sentence I am having a hard time understanding rigorously:

a ball with center v and radius r is the set of vertices at most r hops away from v


For example, if I have a path from v1 to v2 to v3, then it has 3 hops. But if v1 also has v4 as a neighbor and we want a ball radius 3, does it mean that v4 should also be part of the set of radius 3 with center v1?

In fact, is the radius ball defined as follow:

$$ B(v,r) = \{ x \in V : \exists path(v,x) s.t.| path(v,x)| \leq r \}$$

or maybe it should be defined with shortest paths $\delta(v, \cdot)$:

$$ B(v,r) = \{ x \in V : \delta(v,x) \leq r \}$$

i.e. if you can get to a node from v in less that $r$ hops then its part of the radius ball on the graph.


In particular, consider the example. If we have a bounded degree say $d$ and the graph is undirected, if we have the radius be some finite number, do we necessarily have to include everyone's neighbor i.e. consider all the nodes in the degree?

$\endgroup$
  • $\begingroup$ Those latter definitions are what is intended, and they are equivalent. $\endgroup$ – Derek Elkins Apr 24 '16 at 2:15
  • $\begingroup$ @DerekElkins so it has to be all nodes at that distance, so in my example, v2 has to be part of the radius ball? Sorry I know its a simple questions but Im confused :( $\endgroup$ – Pinocchio Apr 24 '16 at 2:16
  • $\begingroup$ @DerekElkins I guess my main worry is, if I say the ball has radius 3 and each node has degree d. Then the number of nodes in the ball have to be $d^3$? Like do we need to include all the nodes that are adjacent to our node every time and we can't skip them? (assume undirected graph) $\endgroup$ – Pinocchio Apr 24 '16 at 2:19
  • 1
    $\begingroup$ Yes, it is all nodes. If $\delta$ returned the length of the shortest path (and $\infty$ if no path exists), you would have a norm. The definition for real numbers and for this would both be an instance of the general concept of "ball" in a metric space. $\endgroup$ – Derek Elkins Apr 24 '16 at 2:21
  • 1
    $\begingroup$ You don't need to include duplicates. For an undirected graph, you would have strictly less than $d^3$ nodes (since some edges would point back at nodes already included.) Indeed, it could be as low as $d+1$ if it was a fully connected graph. $\endgroup$ – Derek Elkins Apr 24 '16 at 2:23
1
$\begingroup$

An undirected (possibly weighted) graph defines a metric space, in which the distance between two vertices $x$ and $y$ is the length of the shortest path between $x$ and $y$; here the length of the path is the sum of the weights on the edges (weights are assumed to be non-negative), or the number of edges if the graph is unweighted. Given a metric, a ball is defined according to your formula.

If the maximal degree is $d$, the number of vertices in a ball of radius $r$ is at most $1 + d(1+\cdots+(d-1)^{r-1})$, which is what you get for a $d$-regular graph.

$\endgroup$
  • 1
    $\begingroup$ I don't have the reputation to comment on or edit Yuval's answer, but the sum in his number of vertices equation is ambiguous-I think he means to say the sum goes from 0 to r-1, so the maximal degree is $$1 + d(\sum_{i=0}^{r-1}(d-1)^i)$$ This comes from the fact that you have your vertex and all d nodes connected to it. Each of those forms a tree with $d-1$ children for each node in the tree and $r$ levels (or $r-1$ "hops"). $\endgroup$ – bschreck Apr 24 '16 at 19:16
0
$\begingroup$

$B(v,r)$ can be defined to be the set of vertices of the graph whose distance to $v$ is at most $r$. Thus $B(v,0) = \{v\}$, and $B(v,1) = \{v\} \cup N(v)$, where $N(v)$ is the set of neighbors of vertex $v$. If $D$ is the diameter of the graph, because every vertex has a distance at most $D$ to $v$, $B(v,D)$ is the entire vertex set $V(G)$ of the graph. We have $B(v,0) \subseteq B(v,1) \subseteq \cdots \subseteq B(v,D)$.

Both the formulae you give for $B(v,r)$ look correct because: there exists an $x-v$ path of length at most $r$ if and only if the length of a shortest $x-v$ path is also at most $r$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.