Godsil-McKay switching and isomorphism

DOI10.13001/1081-3810.2986zbMATH Open1327.05197arXiv1406.4170OpenAlexW1922882632MaRDI QIDQ5502152FDOQ5502152

Willem H. Haemers, Andries E. Brouwer, Aida Abiad

Publication date: 17 August 2015

Published in: The Electronic Journal of Linear Algebra (Search for Journal in Brave)

Abstract: Godsil-McKay switching is an operation on graphs that doesn't change the spectrum of the adjacency matrix. Usually (but not always) the obtained graph is non-isomorphic with the original graph. We present a straightforward sufficient condition for being isomorphic after switching, and give examples which show that this condition is not necessary. For some graph products we obtain sufficient conditions for being non-isomorphic after switching. As an example we find that the tensor product of the $ellimesm$ grid ($ell>mgeq2$) and a graph with at least one vertex of degree two is not determined by its adjacency spectrum.

Full work available at URL: https://arxiv.org/abs/1406.4170

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• On a theorem of Godsil and McKay concerning the construction of cospectral graphs
• Cospectral graphs, GM-switching and regular rational orthogonal matrices of level \(p\)
• Cospectral mates for the union of some classes in the Johnson association scheme
• Godsil-McKay switching for mixed and gain graphs over the circle group
• Cospectral graphs and regular orthogonal matrices of level 2

zbMATH Keywords

cospectral graphsgraph productsgraph isomorphismspectral characterizationGodsil-McKay switching

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Cited In (6)

• Construction of cospectral graphs, signed graphs and \(\mathbb{T}\)-gain graphs via partial transpose
• Equitable switching and spectra of graphs
• Godsil-McKay switching and twisted Grassmann graphs
• Cospectral bipartite graphs with the same degree sequences but with different number of large cycles
• Unification of graph products and compatibility with switching
• An application of Hoffman graphs for spectral characterizations of graphs

This page was built for publication: Godsil-McKay switching and isomorphism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5502152)