Cospectral graphs and regular orthogonal matrices of level 2

A. Abiad, W.H. Haemers

Research output: Contribution to journalArticleScientificpeer-review

Abstract

For a graph Γ with adjacency matrix A, we consider a switching operation that takes Γ into a graph Γ′ with adjacency matrix A′, defined by A′ = QAQ, where Q is a regular orthogonal matrix of level 2 (that is, QQ=I, Q1 = 1, 2Q is integral, and Q is not a permutation matrix). If such an operation exists, and Γ 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 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 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 languageEnglish
Article numberP13
JournalThe Electronic Journal of Combinatorics: EJC
Volume19
Issue number3
Publication statusPublished - 2012

    Fingerprint

Cite this