Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.