2014/06/16 by Aida Abiad, Abiad, Aida, Andries E. Brouwer +3
Computer Science · Mathematics · #Cellular Automata and Applications #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1406.4170
openalex publication_date 2014/06/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ℓ× m grid (ℓ>m≥ 2) and a graph with at least one vertex of degree two is not determined by its adjacency spectrum.