# Inductively defined sequence of graph neighborhoods

I'm trying to solve the following problem:

Let $$v_0$$ be a vertex in a graph $$G$$, and $$D_0 := \{v_0\}$$.

1. For $$n = 1, 2 \dots$$ inductively define $$D_n := N(D_0 \cup D_1 \cup \dots \cup D_{n-1})$$.

2. Show that $$D_n = \{v | d(v_0, v) = n\}$$ and $$D_{n+1} \subseteq N(D_n) \subseteq D_{n-1} \cup D_{n+1}$$ for all $$n \in \mathbb{N}$$.

Here, $$N_G(V') = N(V')$$ is the neighborhood of $$V' \subseteq V(G)$$, and $$d_G(u, v) = d(u, v)$$ is the distance in $$G$$ of two vertices $$u$$, $$v$$.

I'm unable to solve the task because I am not sure if it's correctly defined. Every type of graph seems to be a contradiction to the statements above. Consider for simplicity the following example:

Let $$P$$ be a path, and $$v_0$$ be the central vertex in $$P$$. Then

$$D_0 = \{v_0\}$$,

$$D_1 = N(D_0) = \{v | d(v_0, v) = 1\}$$,

$$D_2 = N(D_0 \cup D_1) = N(\{v_0\} \cup N(\{v_0\})) = \{v | d(v_0, v) \leq 2\}$$,

and for all $$n \geq 2$$ we obtain $$D_n = \{v | d(v_0, v) \leq n\}$$. In particular, it follows that $$V(P) = D_r$$, where $$r$$ is the radius of $$P$$.

This example contradicts both statements in the second part of the task. Can you, please, help me find out, is there anything I am missing or interpreting incorrectly?

You are mixing closed and open neighbourhood. I think when they are stating $$D_n=N(D_0\cup\ldots\cup D_{n-1})$$, they are implying the open neighbourhood

The open neighbourhood $$N(S)$$ of some set of vertices $$S$$ does not include $$S$$. Therefore, using your exampla of the path $$P$$:

$$D_0=\{v_0\}$$

$$D_1=N(D_0)=\{v \mid d(v_0,v)=1\}$$

$$D_2=N(D_0\cup D_1)=\{v \mid d(v_0,v)=2\}$$ and so on.

More precisely if you define $$P$$ as: $$\ldots \ v_{-n} \ldots \ v_{-2} \ v_1 \ v_0 \ v_1 \ v_2 \ldots \ v_n \ldots$$ Then $$D_0=\{v_0\}$$, $$D_1=N(D_0)=\{v_1,v_{-1}\}$$, and $$D_2=N(D_0\cup D_1)= N(\{v_1,v_0,v_{-1}\})=\{v_2,v_{-2}\}$$

Therefore the statements holds as \begin{align*} D_{n+1}=\{v_{n+1},v_{-(n+1)}\} &\subset N(D_n)=N(\{v_{n},v_{-n}\})=\{v_{n+1},v_{n-1},v_{-(n-1)},v_{-(n+1)}\}\\ &\subset D_{n-1} \cup D_{n+1} \end{align*} with an equality in your specific case of $$P$$

• Yes, this. I've seen people use the notation $N(X)$ for open neighbourhood and $N[X]$ for closed neighbourhood. Feb 6, 2019 at 9:17
• Indeed $N(X)$ can mean a few different things, after all this time I am not really sure which is the standard. $N(X)$ could be $S_1 \doteq \{v: vx \in E$ for some $x \in X\}$... $N(X)$ could mean $S_1 \cup X$ or it could mean $S_1 \setminus X$.
– Mike
Feb 6, 2019 at 21:10

It depends on how you define the neighbourhood, but it seems that here it is defined so that $$N(V')$$ comprises the vertices adjacent to some vertex in $$V'$$, excluding vertices in $$V'$$.

So in that case, $$N(D_0\cup D_1)\neq \{v|d(v_0,v)\leq 2\}$$.