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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s