Cospectral Graphs and Regular Orthogonal Matrices of Level 2

Abstract

For a graph $\Gamma$ with adjacency matrix $A$, we consider a switching operation that takes $\Gamma$ into a graph $\Gamma'$ with adjacency matrix $A'$, defined by $A'=Q^\top A Q$, where $Q$ is a regular orthogonal matrix of level $2$ (that is, $Q^\top Q=I$, $Q$1 $=$ 1, $2Q$ is integral, and $Q$ is not a permutation matrix). If such an operation exists, and $\Gamma$ is nonisomorphic with $\Gamma'$, then we say that $\Gamma'$ is semi-isomorphic with $\Gamma$. Semi-isomorphic graphs are $\mathbb {R}$-cospectral, which means that they are cospectral and so are their complements. Wang and Xu [On the asymptotic behavior of graphs determined by their generalized spectra, Discrete Math. 310 (2010)] expect that almost all pairs of nonisomorphic $\mathbb {R}$-cospectral graphs are semi-isomorphic.

Regular orthogonal matrices of level $2$ have been classified. By use of this classification we work out the requirements for this switching operation to work in case $Q$ has one nontrivial indecomposable block of size $4$, $6$, $7$ or $8$. Size $4$ corresponds to Godsil-McKay switching. The other cases provide new methods for constructions of $\mathbb {R}$-cospectral graphs. For graphs with eight vertices all these constructions are carried out. As a result we find that, out of the 1166 graphs on eight vertices which are $\mathbb {R}$-cospectral to another graph, only 44 are not semi-isomorphic to another graph.