Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  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!

share|improve this question
    
First of all, you could just look most of this up in any graph theory book probably. I think the definitions are pretty clear and standard. Also, are you talking about graphs that have loops or directed edges, or not? –  Graphth Nov 8 '12 at 20:50
    
@Graphth: It may have loops or directed edges. –  Tim Nov 8 '12 at 20:53

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
+1 But... Perhaps your first three sentences would best serve as comments to the question? –  amWhy Nov 8 '12 at 20:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.