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 Cancel reply

Enter your comment here...

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

Email (required) (Address never made public)

Name (required)

Website

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

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

Cancel

Connecting to %s

Share this:

Like this:

Related

Leave a Reply Cancel reply