1
$\begingroup$

$G_1$

$G_2$

Whether these two graphs are nonisomorphic? They have same number vertices, same regularity, they are cospectral (means: they have same same set of adjacency eigenvalues). I have taken powers of their adjacency matrices and observed that each number in its entries is appearing the same number of times. So whether I could conclude, they are isomorphic!

$\endgroup$
  • $\begingroup$ There are only 9 vertices, can't you just brute force it? $\endgroup$ – 5xum Mar 3 '16 at 14:41
  • $\begingroup$ We have $C_4 \dot \cup K_1$ and $K_{1,4}$ are cospectral but not isomorphic. Cospectral is necessary but not sufficient for isomorphism. $\endgroup$ – ml0105 Mar 3 '16 at 14:52
3
$\begingroup$

$G_1^C$

$G_2^c$

Clearly the complements are isomorphic so both the graphs in Figure-1 and Figure-2 are isomorphic.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.