### Abstract

For a graph

Regular orthogonal matrices of level

**Γ**with adjacency matrix*, we consider a switching operation that takes***A****Γ**into a graph**Γ′**with adjacency matrix*, defined by***A′****=***A′**, where***Q**^{⊤}AQ*is a regular orthogonal matrix of level***Q****2**(that is,*,***Q**^{⊤}Q=I**=***Q1***1, 2Q**is integral, and**is not a permutation matrix). If such an operation exists, and***Q***Γ**is nonisomorphic with**Γ′**, then we say that**Γ′**is semi-isomorphic with**Γ**. Semi-isomorphic graphs are 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 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**has one nontrivial indecomposable block of size***Q***4, 6, 7**or**8**. Size**4**corresponds to Godsil-McKay switching. The other cases provide new methods for constructions of 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 R-cospectral to another graph, only 44 are not semi-isomorphic to another graph.Original language | English |
---|---|

Article number | P13 |

Journal | The Electronic Journal of Combinatorics: EJC |

Volume | 19 |

Issue number | 3 |

Publication status | Published - 2012 |