5
$\begingroup$
  1. In a graph G, are the neighbours of a vertex defined to exclude the vertex?

    Do we need to explicitly distinguish between "the neighbours of a vertex $v$" and "the neighbours of a vertex $v$ in $G - v$"?

    Also is there a concept similar to neighbourhood of a point in a topological space?

    If there is an edge from the vertex to itself, is the vertex the neighbour of itself?

  2. Are the neighbours of a subset of vertices also defined to be outside the subset?

    If there are edges between vertices in the subset, does this affect the neighbours of the subset of vertices?

When people wrote $N(v)$ for a vertex $v$, or $N(S)$ for a subset $S$ of vertices, does it usually include $v$ or $S$?

My questions are for the most consensus usage.

Thanks!

  • 0
    @Graphth: It may have loops or directed edges.2012-11-08

1 Answers 1

7

If you are talking about simple graphs with no loops or directed edges, then usually $N(u)$ denotes the open neighborhood of $u$, which means all the actual neighbors of $u$ but not $u$ itself. And, $N[u]$ denotes the closed neighborhood of $u$, which means all the neighbors of $u$ AND $u$ itself.

In any case, if loops are allowed or not, the neighbors of a vertex mean the vertices that are adjacent to that vertex. So, if the vertex is connected to itself via a loop, then the vertex would be its own neighbor. And, if the vertex is not connected to itself via a loop, then it is not its own neighbor.

If you are talking directed graphs, then you talk about the out-neighborhood and the in-neighborhoods separately. That is, the out-neighborhood, $N^+(v)$ is the set of vertices adjacent from $v$ (from meaning directed away from $v$), and the in-neighborhood, $N^-(v)$ is the set of vertices adjacent to $v$ (to meaning directed toward $v$). If the graph is directed and allows loops, then an edge from $v$ to $v$ would mean $v$ would be in both of these neighborhoods.

I'm not sure if a neighborhood of a set of vertices (bigger than 1) is very standard. Maybe???

In topology, a neighborhood of a point is any open set containing that point. I haven't studied this at all but you could define a topology based on this. Let us call the empty set of vertices open. Let us call the (open) neighborhood of any vertex to be open. And, let us call any union of open sets open, and any finite intersection of open sets open. This is definitely a topology on the set of vertices of a graph.

For example, if your graph is $K_n$, this leads to open sets being $V(K_n)$ and $\emptyset$ and nothing more. If your graph is the empty graph, then you have the discrete topology, i.e., any subset of the vertices is open.

  • 0
    I think you made a mistake; if our graph is the empty graph, then the open sets are just the set of vertices and $\emptyset$, and if our graph is $K_n$, _then_ (though showing this result is slightly harder, it can be done) any subset of the vertices is open.2018-05-30