2
$\begingroup$

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?

Thanks!

  • 0
    @All: Thanks for the comments. I've edited the post to reflect a few small changes.2011-06-23

0 Answers 0