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?


  • 2
    $\begingroup$ 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)$. $\endgroup$ – Arturo Magidin Jun 22 '11 at 20:48
  • 3
    $\begingroup$ 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. $\endgroup$ – Nicolas Villanueva Jun 22 '11 at 20:53
  • $\begingroup$ Are the graphs undirected? $\endgroup$ – Qiaochu Yuan Jun 22 '11 at 20:56
  • $\begingroup$ Just a half-baked thought, but perhaps you will still have an isomorphism if (and only if?) the graphs are vertex transitive. $\endgroup$ – Austin Mohr Jun 22 '11 at 23:27
  • $\begingroup$ @All: Thanks for the comments. I've edited the post to reflect a few small changes. $\endgroup$ – user02138 Jun 23 '11 at 9:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.