Vertex

graph-theory

Definition

Vertex

A vertex is a fundamental unit in graph theory, representing an individual point where two or more edges meet in a graph.

The number of vertices of a graph can be denoted as ${\alpha }_0(G)$ or $|V(G)|$.

Adjacency

Two vertices $v_1,v_2\in V$ are called adjacent if there exists an edge inbetween.

The edge connecting $v_1$ and $v_2$ is called the incident edge of $v_1$ and $v_2$.

Neighbours

Undirected Neighbours

The set of adjacent vertices of a vertex $v$ in an undirected graph $G$ is denoted as:

$$\Gamma (v)=\{w\in V(G)\mid vw\in E(G)\}$$

The number of neighbours is given by:

$$d(v)=|\Gamma (v)|$$

Directed Neighbours

The set of successors of a vertex $v$ in a directed graph is given by:

$${\Gamma }^{+}(v)=\{w\in V(G)\mid (v,w)\in E(G)\}$$

The set of predecessors of a vertex $v$ in a directed graph is given by:

$${\Gamma }^{-}(v)=\{w\in V(G)\mid (w,v)\in E(G)\}$$

The number of successors and predecessors is given by:

$$\begin{array}{rl}{d}^{+}(v)& =|{\Gamma }^{+}(v)|=\text{\# of successors}\\ & \\ d^{-}(v)& =|{\Gamma }^{-}(v)|=\text{\# of predecessors}\end{array}$$

Degree

Degree

The degree $d(v)$ of a vertex $v$ is the number of neighbours of $v$:

$$d(v)=|\Gamma (v)|$$

The minimum degree of a graph $G$ is the smallest degree of any vertex in $G$:

$$\delta (G)=\underset{v\in V(G)}{\min }d(v)$$

The maximum degree of a graph $G$ is the largest degree of any vertex in $G$:

$$\Delta (G)=\underset{v\in V(G)}{\max }d(v)$$

Adjacency Matrix

Definition

Adjacency Matrix

An adjacency matrix is a square matrix used to represent a graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

$$A=(a_{ij}{)}_{i,j}=1,\dots n\text{with}{a}_{ij}=\{\begin{array}{ll}1& \text{if}(v_i,v_j)\in E\\ 0& \text{else}\end{array}$$

For undirected graphs, the adjacency matrix is symmetric.

Link to original