Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

2 Answers

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|improve this answer
add comment

$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|improve this answer
add comment

Your Answer

 
discard

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.