Neighbourhood, Degrees, and Degree Sequences
The Neighbourhood of a Vertex
Definition: The Neighbourhood of the vertex $x \in V(G)$ is the set of all vertices which are adjacent to $x$. For the graph $G = (V(G), E(G))$ we have that the neighbourhood of $x$ denoted $N_{G} (x)$ is $\displaystyle{N_{G}(x) = \left\{ {y \in V(G) : {x, y} \in E(G)}\right\}}$. |
When understood, the notation $N_G(x)$ can be replaced with $N(x)$.
For example, the following graph:
The neighbourhood of vertex $x$ is $N_G(x) = \{a, b, c, d \}$ since the vertex $x$ forms an edge with $a, b, c$ and $d$. The neighbourhood of vertex $a$ is $N_G(a) = \{x, b\}$.
The Degree of a Vertex
Definition: The Degree of a vertex $x$ in a graph $G = (V(G), E(G))$, denoted $\mathrm{deg} (x)$ is the number of vertices adjacent to $x$. Equivalently, the degree of $x$ is the size of the neighbourhood of $x$, that is, $\mathrm{deg}(x) = \mid N_G(x) \mid$. |
For example, from our graph above, the degree of vertex $x$ is $\mathrm{deg}(x) = 4$. The degree of vertex $a$ is $\mathrm{deg}(a) = 2$.
The Degree Sequence of a Graph
Definition: The Degree Sequence of a graph $G = (V(G), E(G))$ is the ordered sequence of degrees of vertices $x \in V(G)$ from smallest degree to greatest degree. |
From the graph from earlier we have that the degrees of each vertex are given in the following table:
Vertex | Degree |
---|---|
$x$ | $\mathrm{deg}(x) = 4$ |
$a$ | $\mathrm{deg}(a) = 2$ |
$b$ | $\mathrm{deg}(b) = 2$ |
$c$ | $\mathrm{deg}(c) = 2$ |
$d$ | $\mathrm{deg}(d) = 2$ |
So the degree sequence for our graph is $(2, 2, 2, 2, 4)$. Notice that the degree sequence allows for repetition as some vertices may have the same degree.