# Graphs with commuting adjacency matrices

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?

-

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$.