Let A and B be adjacency matrix of two undirected simple graphs. Can we assign some combinatorial interpretations to this pair of graphs if A and B commute?
Graphs with commuting adjacency matrices
2 Answers
I find it hard to think of anything useful. The adjacency matrix of a graph and its complement commute if and only if the graph is regular. An association scheme is a partition of the edges into graphs whose adjacency matrices commute (along with other conditions). There is a large literature on these, but I do not recall anything that relates properties of different graphs in the partition.
Note also that one graph has many different adjacency matrices in general ($n!/|\mathrm{Aut}(G)|$) and these may or may not commute with each other. And some of these might commute with the adjacency matrix of a second graph, and the others not.
$AB=BA$ says that for vertices $u,v$ there are just as many paths $u-w-v$ with $uw\in A$ and $vw\in B$ as with $uv\in B$ and $vw\in A$.