5
$\begingroup$

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?

$\endgroup$

2 Answers 2

4
$\begingroup$

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$

$\endgroup$
2
  • 1
    $\begingroup$ Yes, this. I've seen people use the notation $N(X)$ for open neighbourhood and $N[X]$ for closed neighbourhood. $\endgroup$ Feb 6, 2019 at 9:17
  • $\begingroup$ 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$. $\endgroup$
    – Mike
    Feb 6, 2019 at 21:10
3
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .