Neighbourhood in graph theory
In graph theory I stumbled across the definition of the neighborhood;
Def."The set of all neighbors of a vertex $v$ of $G = (V , E)$, denoted by $N(v)$, is called the neighborhood of $v$. If $A$ is a subset of $V$, we denote by $N(A)$ the set of all vertices in $G$ that are adjacent to at least one vertex in $A$. So, $N (A) = \bigcup_{v\in A} N(v)$"
And I'm not sure I understand it correctly.
Let's say we have a set of vertices $V=\{a,b,c,d\}$ and a set of edges $E=\{\{a,b\},\{a,c\},\{b,c\},\{c,d\}\}$.
Now let the A be a subset of V such that $A=\{a,b\}$ which is illustrated in the picture:
Now, following the definition, what would the neighbourhood of N(A) be?
Is it:
$$ N(A) = \bigcup_{v\in A} N(v) $$$$ N(A) = N(a)\cup N(b)$$$$ N(A) = \{b,c\}\cup \{a,c\} $$$$ N(A) = \{a,b,c\}$$
Is this the correct understanding or am I missing something?
$\endgroup$1 Answer
$\begingroup$When you stumbled across this definition, did you happen to see the definition of "adjacent" lying around somewhere nearby? In particular, is every vertex adjacent to itself?
Your final answer is correct one way or the other. But your intermediate steps might be incorrect. In particular, if it is true that every vertex is adjacent to itself then $N(a)=\{a,b,c\}$ and $N(b)=\{a,b,c\}$.
$\endgroup$ 3
