# Neighbourhood of a vertex

Перейти к:навигация, поиск

Neighbourhood of a vertex --- окрестность вершины.

For each vertex $v$ the set $N(v)$ of vertices which are adjacent to $v$. The other name is open neighbourhood. The closed neighbourhood is $N[v] = N(v) \cup \{v\}$.

For disjoint subsets $A$ and $B$ of $V$, we define $[A,B]$ to be the set of all edges that join a vertex of $A$ and a vertex of $B$. Furthermore, for $a \in A$, we define the private neighbourhood $pn(a,A,B)$ of $a$ in $B$ to be the set of vertices in $B$ that are adjacent to $a$ but to no other vertex of $A$; that is, $pn(a,A,B) = \{b \in B| N(b) \cap A = \{a\}\}$.

Given a digraph $D$, let $x,y$ be distinct vertices in $D$. If there is an arc from $x$ to $y$, then we say that $x$ dominates $y$ and write $x \rightarrow y$ and call $y$ (respectively, $x$) an out-neighbour (out-neighborhood) (respectively, an in-neighbour (in-neighborhood)) of $x$ (respectively, $y$). We let $N^{+}(x), N^{-}(x)$ denote the set of out-neighbours, respectively, the set of in-neighbours of $x$ in $D$. Define $N(x)$ to be $N(x) = N^{+}(x) \cup N^{-}(x)$.

$D$ is an out-semicomplete digraph (in-semicomplete digraph) if $D$ has no pair of non-adjacent vertices with a common in-neighbour or a common out-neighbour. $D$ is a locally semicomplete digraph if $D$ is both out-semicomplete and in-semicomplete.