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:

Screen%20Shot%202014-02-08%20at%206.29.30%20PM.png

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.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License