Sign up ×
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.

Two weighted directed graphs $G_1$ and $G_2$ are (graph) isomorphic if and only if there is a permutation matrix $P$ such that the corresponding adjacency matrices $A_1$ and $A_2$ are $P$-similar, e.g., $A_2 = P A_1 P^{-1}$.

Question: Is there a similar equivalence which relaxes the similarity condition somewhat? That is, what do we call two weighted directed graphs related by the following: There are two permutations $P$ and $Q$ such that $A_2 = P A_1 Q^{-1}$? What numerical invariants are conserved by this equivalence besides the absolute value of the determinant?


share|cite|improve this question
The determinant is not preserved: say you take $Q$ to be the identity, and $P$ to be the matrix you get by exchanging two rows of the identity. Then $\det(Q)=1$, $\det(P)=-1$, so $\det(A_2)=-\det(A_1)$. – Arturo Magidin Jun 22 '11 at 20:48
If we are allowed to choose ANY two permutations $P$ and $Q$, then the only thing conserved in $A_2$ is the total vertex degree. – Nicolas Villanueva Jun 22 '11 at 20:53
Are the graphs undirected? – Qiaochu Yuan Jun 22 '11 at 20:56
Just a half-baked thought, but perhaps you will still have an isomorphism if (and only if?) the graphs are vertex transitive. – Austin Mohr Jun 22 '11 at 23:27
@All: Thanks for the comments. I've edited the post to reflect a few small changes. – user02138 Jun 23 '11 at 9:11

Your Answer


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

Browse other questions tagged or ask your own question.