2
$\begingroup$

Let $A_G,A_H$ be the adjacency matrices of two non-isomorphic graphs.

Let $P$ be orthogonal matrix with rational entries.

Is it possible $A_G = P^{-1}A_H P$?

Paper gives algorithm for recognizing rational orthogonal similarity which appears to involve computing the splitting field, which in sage is quite slow.

Is the algorithm in the paper polynomial?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Yes, there are. The smallest pair are the subdivision graph of $K_{1,3}$ and $C_6$ with an isloated vertex. There are many more, look up "Godsil-McKay switching". The original source is at http://cs.anu.edu.au/~Brendan.McKay/papers/GodsilMcKayCospectral.pdf

It is not impossible that "most" pairs of cospectral graphs are rationally cospectral.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks. What is reference for the explicit orthogonal matrix? $\endgroup$
    – joro
    Mar 23, 2015 at 12:56
  • 1
    $\begingroup$ @joro: See Theorem 2.7 in the paper. $\endgroup$
    – Chris Godsil
    Mar 23, 2015 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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