I'm solving the exercises in chapter 2 from Graph Theory with Algorithms and its Applications. So far, for isomorphism I just write all the edges and try to find the patterns, which for small graphs is enough. For these 2 10-vertices 30-edges graph I think I need something more scalable. I tried 'translating' both graphs to a unified structure, but off course if one vertx changes name the graph will also look different. I wrote the adjacency matrix trying to find a pattern, and there's a column that makes me suspicious these two may not be isomorphic. However, I could always change the name of a vertex to make columns look a bit more similar. Anyway, I found that two graphs (A,B) are isomorphic if A = PBP(t) where P is a permutation matrix, and P(t) is its transpose.
Since det(P) = 1 or -1 = det(P(t)) and det(AB) = det(A)*det(B) then if A and B are isomorphic:
det(A) = 1|-1*det(B)*1|-1
det(A)=det(B)
could two adjacency matrices have the same determinant and not be isomorphic? or is equality in the determinant a sufficient condition (and much more scalable) for isomorphism?
Best,
Sergio
Best Answer
It is indeed true that the adjacency matrix of isomorphic graphs will have the same determinant. Indeed, if $A = PBP^T$ for a permutation matrix $P$, then $$ \det(A) = \det(P) \det(B) \det(P^T) = \det(P)^2 \det(B) = \det(B). $$ In fact, we can say more: because $A$ and $B$ are similar matrices, they will have the same eigenvalues. Note that if two matrices have the same eigenvalues, then they automatically have the same determinant.
The converse does not hold: if $A,B$ are the adjacency matrices of two graphs and we have $\det(A) = \det(B)$, it does not necessarily hold that the graphs are isomorphic. In fact, even if $A$ and $B$ have the same eigenvalues, it does not necessarily hold that the graphs are isomorphic. Examples of this phenomenon are called isospectral (or cospectral) pairs of graphs.