Inductively defined sequence of graph neighborhoods

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$


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\}$.

Tags:

Graph Theory