Take the 2-minute tour ×
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?

Thanks!

share|improve this question
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)$. –  Arturo Magidin Jun 22 '11 at 20:48
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. –  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

 
discard

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

Browse other questions tagged or ask your own question.