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
    Commented Mar 23, 2015 at 12:56
  • 1
    $\begingroup$ @joro: See Theorem 2.7 in the paper. $\endgroup$
    – Chris Godsil
    Commented Mar 23, 2015 at 13:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .