# Nomenclature of matrices used in graph theory

So far I've come across a bunch of different terms for matrices used in graph theory - adjacency matrix, connectivity/connection matrix, vertex matrix, etc.

Are there any differences between these matrices or are all of these terms just referring to the same thing?

-
You might have an Edge connectivity matrix which is different from the adjacency matrix (call that the vertex connectivity matrix): The edge-connectivity matrix, denoted by $^eχ$, of a graph $G$ is the vertex-conectivity matrix of the corresponding line graph $\text{L}(G)$. –  draks ... Jan 11 '13 at 12:55
There is also the incidence matrix whose entry $m_{ij}$ is the number of times that vertex $i$ and edge $j$ are incident. –  PAD Jan 11 '13 at 13:23

Some important matrices for a graph $G=(V,E)$ are the following
Adjacency matrix: This matrix $A$ denotes the adjacency between vertices. It is a $|V|\times|V|$ matrix and its entries $a_{ij}$ are defined as $$a_{ij}:=\begin{cases} 1 & \text{if (v_i,v_j)\in E} \\ 0 & \text{otherwise} \end{cases}.$$ Notice that if $G$ is undirected $A$ is symmetric. Taking the power $A^k$ gives you a matrix that denotes the number of paths from $v_i$ to $v_j$ at entry $i,j$.
Laplacian matrix: For this matrix $L$ consider the diagonal matrix $D=\text{diag}(d_1,d_2,\ldots)$, for $d_i$ being the vertex degree of $v_i$. Then $L:=D-A$. The matrix $L$ is the most important object studied is spectral graph theory. It has many nice properties, for example its cofactors give the number of spanning trees of $G$. There is also a normalized version of the Laplace matrix.
Incidence matrix: This is a $|V|\times |E|$ matrix $B$, whose entries $b_{ij}$ ar defined as $|V|\times|V|$ matrix and its entries $a_{ij}$ as $$b_{ij}:=\begin{cases} 1 & \text{if v_i\in V$$ is incident to $e_j\in E$} \\ 0 & \text{otherwise} \end{cases}  Sometimes you consider incidence matrices $\vec{B}$ for Graphs with oriented edges. In this case you would change the $1$ entries to $-1$ if the edge points away from a vertex. Notice that Notice that $\vec{ B}\, \vec{B}^T=L$.
Is there a simple way to count the number of walks (no loops allowed) from $v_i$ to $v_j$? –  Calvin Lin Jan 11 '13 at 15:28