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!

  • 2
    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)$.2011-06-22
  • 3
    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.2011-06-22
  • 0
    Are the graphs undirected?2011-06-22
  • 0
    Just a half-baked thought, but perhaps you will still have an isomorphism if (and only if?) the graphs are vertex transitive.2011-06-22
  • 0
    @All: Thanks for the comments. I've edited the post to reflect a few small changes.2011-06-23

0 Answers 0