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?

$\endgroup$
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.

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

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.