What terminology to use for this graph neighborhood construction?

35 Views Asked by At

I have a question about terminology. Given a node $n$ in a graph, is there a name for the set of nodes that are the node's neighbors or the neighbors of these neighbors? Something like "2-neighborhood" or "super neighborhood"?

What about the set of nodes that are $k$ edges away from $n$? Can this be called a "$k$-neighborhood"?

Many thanks for any feedback or guidance.

1

There are 1 best solutions below

0
On BEST ANSWER

What I have seen in many papers is that, if $N(v)$ is the set of neighbours of v, than $N_{2}(v) = \{ w \in V: \forall u \in N(v), (u,w)\in E\}$ would be the set of nodes, that are at most "two edges away" from v. Thus, expanding this idea for the set of nodes that are "k-away", would be something like: $N_{k}(v) = \{ w \in V: \forall u \in N_{k-1}(v), (u,w)\in E\}$. If you want to make sure that those nodes are exactly, for example two edges away, you would also have to add some constraint to it, something like $N_{2}(v) = \{ w \in V: \forall u \in N(v), (u,w)\in E\ \land w \notin N(v) \}$, thus having nodes, that are not adjacent to v and thus being exactly 2 edges away.