Graph with no-selfloop, no-multi-edges, unweighted.

**directed**

For directed graph Adjacency matrix is a non-symmetric matrix $A_{in}$ considering indegree or $A_{out}$ considering outdegree. Degree matrix $\Delta$ is diagonal matrix $\Delta=\Delta_{in}+\Delta_{out}$. The diagonal elements are sum of indegree and outdegree. The oriented incidence matrix $B_{oriented}$, $N\times M$. $b_{im}=1$ if edge $m$ start from $i$. $b_{im}=−1$ if edge $m$ ended to $i$. $b_{im}=0$ otherwise.

$\Delta-A_{in}\neq\Delta-A_{out}\neq B_{oriented}B_{oriented}^T$

**undirected**

For undirected graph and oriented incidence matrix $B_{oriented}$ have dimension $N\times 2M$. $B_{oriented}B_{oriented}^T=2\Delta-2A$.

unoriented incidence matrix: $b_{im}=1$ if link $m$ incident -- start from $i$ or end to $i$. $b_{im}=0$ otherwise. $B_{unoriented}B_{unoriented}^T=\Delta+A$.

**Problem**

When Laplacian matrix $L=BB^T=\Delta-A$? Many definitions I saw do not give clear assumption in the context. Say, undirected or directed, oriented or unoriented, $A_{in}$ or $A_{out}$ or $A$? or whatever ... ?

Any references would be greatly appreciated. Thank you.

**EDIT**

The reference which make me confused is `2011, P.V. Mieghem, Graph Spectra for Complex Networks`

**Chapter 2 Algebraic graph theory** P14. **2.** **The relation between adjacency and incidence matrix is given by the admittance
matrix or Laplacian $Q=BB^T=\Delta-A$**

**EDIT2**

## 1. adjacency matrix

unweighted, nomultiple-edges $A$, $N\times N$, noselfloop $a_{ii}=0$

### 1.1 directed

$A=\begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & 0 \end{pmatrix}$

### 1.2 undirected

$A=\begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 1\\ 1 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 1\\ 1 & 1 & 0 & 0 & 1 & 0 \end{pmatrix}$

## 2. incidence matrix $B$,

$N\times M$, $M$ are edges. lexicographically ordered.

### 2.1 directed

$N\times M$, $N=6$, $M=9$,

$e_1=1\rightarrow 2$, $e_2=1\rightarrow 3$, $e_3=1\leftarrow 6$,

$e_4=2\rightarrow 3$, $e_5=2\leftarrow 5$,$e_6=2\rightarrow 6$,

$e_7=3\rightarrow 4$,

$e_8=4\leftarrow 5$,

$e_9=5\leftarrow 6$

$$B_{oriented}=\begin{pmatrix} 1 & 1 & -1 & 0 & 0 & 0 & 0 & 0 & 0\\ -1 & 0 & 0 & 1 & -1 & 1 &0 & 0 & 0\\ 0 & -1 & 0 & -1 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & -1 & -1 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & -1\\ 0 & 0 & 1 & 0 & 0 & -1 & 0 & 0 & 1 \end{pmatrix}$$

### 2.2 undirected

* (oriented)* $N\times 2M$

$N=6$, $M=18$,

$e_1=1\rightarrow 2$, $e_2=1\leftarrow 2$, $e_3=1\rightarrow 3$,

$e_4=1\leftarrow 3$, $e_5=1\rightarrow 6$, $e_6=1\leftarrow 6$,

$e_7=2\rightarrow 3$, $e_8=2\leftarrow 3$, $e_9=2\rightarrow 5$,

$e_{10}=2\leftarrow 5$, $e_{11}=2\rightarrow 6$, $e_{12}=2\leftarrow 6$,

$e_{13}=3\rightarrow 4$, $e_{14}=3\leftarrow 4$,

$e_{15}=4\rightarrow 5$, $e_{16}=4\leftarrow 5$,

$e_{17}=5\rightarrow 6$, $e_{18}=5\leftarrow 6$

$$B_{oriented}=\begin{pmatrix} 1 & -1 & 1 & -1 & 1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 & 0 & 0 & 1 & -1 & 1 & -1 & 1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & -1 & 1 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 1 & -1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 1 & -1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & -1 & 1 & 1 & -1 \\ 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & -1 & 1\\ \end{pmatrix}$$

$$(oriented)~b_{im}= \begin{cases} 1, & \text{if link $e_m=i\rightarrow j$} \\ -1, & \text{if link $e_m=i\leftarrow j$} \\ 0, & \text{otherwise} \end{cases}$$

* (unoriented)* $N\times M$

$e_1=1 - 2$, $e_2=1 - 3$, $e_3=1 - 6$,

$e_4=2 - 3$, $e_5=2 - 5$,$e_6=2 - 6$,

$e_7=3 - 4$,

$e_8=4 - 5$,

$e_9=5 - 6$

$$B_{unoriented}=\begin{pmatrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 1 & 1 & 1 &0 & 0 & 0\\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1\\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \end{pmatrix}$$

$$(unoriented)~b_{im}= \begin{cases} 1, & \text{if link $e_m=i - j$ incident} \\ 0, & \text{otherwise} \end{cases}$$

## 3. degree matrix

$\Delta_{ii} =deg(i) = \sum_j A_{ij}$. $\Delta_{ij}=0$, $i\neq j$

### 3.1 directed

$\begin{pmatrix} 2＋1 & 0 & 0 & 0 & 0 & 0\\ 0 & 2＋2 & 0 & 0 & 0 & 0\\ 0 & 0 & 1＋2 & 0 & 0 & 0\\ 0 & 0 & 0 & 0＋2 & 0 & 0\\ 0 & 0 & 0 & 0 & 2＋1 & 0\\ 0 & 0 & 0 & 0 & 0 & 2＋1 \end{pmatrix}$

### 3.2 undirected

$\begin{pmatrix} 3 & 0 & 0 & 0 & 0 & 0\\ 0 & 4 & 0 & 0 & 0 & 0\\ 0 & 0 & 3 & 0 & 0 & 0\\ 0 & 0 & 0 & 2 & 0 & 0\\ 0 & 0 & 0 & 0 & 3 & 0\\ 0 & 0 & 0 & 0 & 0 & 3 \end{pmatrix}$

## 4. Laplacian matrix

### 4.1 directed

$B_{oriented}B_{oriented}^T$

$\begin{pmatrix} 3 & -1 & -1 & 0 & 0 & -1\\ -1 & 4 & -1 & 0 & -1 & -1\\ -1 & -1 & 3 & -1 & 0 & 0\\ 0 & 0 & -1 & 2 & -1 & 0\\ 0 & -1 & 0 & -1 & 3 & -1\\ -1 & -1 & 0 & 0 & -1 & 3 \end{pmatrix}$

### 4.2 undirected

**(oriented)**

$B_{oriented}B_{oriented}^T=2\Delta -2A$

$\begin{pmatrix} 6 & -2 & -2 & 0 & 0 & -2\\ -2 & 8 & -2 & 0 & -2 & -2 \\ -2 & -2 & 6 & -2 & 0 & 0 \\ 0 & 0 & -2 & 4 & -2 & 0 \\ 0 & -2 & 0 & -2 & 6 & -2 \\ -2 & -2 & 0 & 0 & -2 & 6 \end{pmatrix}$

**(unoriented)**

$B_{unoriented}B_{unoriented}^T=\Delta + A$

$\begin{pmatrix} 3 & 1 & 1 & 0 & 0 & 1\\ 1 & 4 & 1 & 0 & 1 & 1\\ 1 & 1 & 3 & 1 & 0 & 0\\ 0 & 0 & 1 & 2 & 1 & 0\\ 0 & 1 & 0 & 1 & 3 & 1\\ 1 & 1 & 0 & 0 & 1 & 3 \end{pmatrix}$

Laplacian matrixby $D−A$, you must usesymmetric adjacency matrixwhich is come fromundirected graph (section 1.2)not directed graph (section 1.1). Now: $L=\tilde{D}\tilde{D}^\intercal =D−A$ $\endgroup$