There seems to be two conventions for how to write the adjacency matrix of an undirected graph containing a loop. One convention is to have the loop contribute 2 to the corresponding entry in the adjacency matrix. This has the nice effect of still being consistent with the degree of a vertex simply being the corresponding row or column sum. There is another convention though to have the loop contribute 1 to the corresponding entry in the adjacency matrix. I was wondering if there are any particular justifications for this choice i.e. properties of the adjacency matrix that this allows for.
[Math] Why make a (single) loop correspond to an entry of 1 in the adjacency matrix of an undirected graph
adjacency matrixgraph theory
Related Question
- [Math] How to construct the graph from an adjacency matrix
- [Math] Principal EigenVector of an Adjacency matrix of an undirected graph
- Graph Theory – Invertibility of the Adjacency Matrix of a Graph
- Graph Theory – Finding Path-Lengths by the Power of Adjacency Matrix
- [Math] Sum of elements of square of adjacency matrix of a graph
- Can we recover the adjacency matrix of a graph from its square
Best Answer
I assume that anyone who takes the convention that loops are written as $1$ in the adjacency matrix also takes the convention that loops contribute $1$ to the degree of a vertex. This has both advantages and drawbacks:
If $A$ is the adjacency matrix, then the $(i,j)^{\text{th}}$ entry of $A^n$ counts the number of length-$n$ paths from $i$ to $j$. In the context of this application, I'd probably want loops to be represented by a $1$. Putting a $2$ in the $(i,i)^\text{th}$ entry of $A$ to indicate a loop would introduce a factor of $2$ in paths through $i$ that take that loop: essentially, they can take the edge "forward from $i$ to $i$" or "backward from $i$ to $i$". I'm sure this makes sense sometimes, but by default I wouldn't want this behavior.
(For example, if $G$ is the graph on two vertices $\{0,1\}$ with an edge between $0$ and $1$ and a loop at $0$, paths in $G$ should correspond to binary strings with no two consecutive $1$'s, which are enumerated by the Fibonacci numbers. Powers of the adjacency matrix of $G$ only reflect this if the loop at $0$ corresponds to a $1$ in the adjacency matrix.)