A Property of the Incidence Matrix of Directed Graphs

Let $\partial$ be the $m \times n$ incidence matrix of a directed graph $G$, with $m$ vertices and $n$ edges, where

$\partial_{ij}=\begin{cases} -1, & \text{vertex }i \text{ is the "source" of edge } j\\ 0, & \text{otherwise}\\ 1, & \text{vertex }i \text{ is the "sink" of edge } j \end{cases}$.

Then, for $M=\partial \partial^{T}$, we find that $M$ is an $m \times m$ matrix where

$M_{ik}=\sum_{j=1}^{n}\partial_{ij}\partial_{jk}=\begin{cases} M_{ik}=deg(v_{i}), & i=k\\ M_{ik}= -adj(v_{i}, v_{k}), & i\neq k \end{cases}$,

$deg(v_{i})$ is the degree of vertex $i$, and

$adj(v_{i}, v_{k}) = \begin{cases} 1, & \text{there exist an edge from the vertex } i \text{ to the vertex } k\\ 0, & \text{otherwise} \end{cases}$.

Hence $M = D - A$ where $D$ is the degree matrix of $G$ and $A$ is the adjacency matrix of $G$.

In the case of undirected graphs, assuming

$\partial_{ij}=\begin{cases} 1, & \text{vertex } i \text{ is connected to edge } j\\ 0, & \text{otherwise} \end{cases}$,

then $M = D + A$.

Categories: