Vertex

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)|$.

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 finite graph $G=(V,E)$. For a graph with $|V|=n$ vertices, the adjacency matrix $A\in \{0,1{\}}^{n\times n}$ is defined such that:

$$A_{ij}=\{\begin{array}{ll}1& \text{if }\{v_i,v_j\}\in E\\ 0& \text{otherwise}\end{array}$$

Link to original