Godsil-McKay switching and isomorphism,

Aida Abiad, A.E. Brouwer, W. H. Haemers

Research output: Contribution to journalArticleScientificpeer-review

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 sucient condition for being isomorphic after switching, and give examples which show that this condition is not necessary. For some graph products we obtain sucient conditions for being non-isomorphic after switching. As an example we nd that the tensor product of the grid L(';m) (' > m 2) and a graph with at least one vertex of degree two is not determined by its adjacency spectrum.
Original languageEnglish
Pages (from-to)4-11
JournalElectronic Journal of Linear Algebra
Volume28
DOIs
Publication statusPublished - 2015

Fingerprint

Isomorphism
Graph in graph theory
Graph Products
Adjacency
Adjacency Matrix
Tensor Product
Isomorphic
Grid
Necessary
Vertex of a graph

Cite this

Abiad, Aida ; Brouwer, A.E. ; Haemers, W. H. / Godsil-McKay switching and isomorphism,. In: Electronic Journal of Linear Algebra. 2015 ; Vol. 28. pp. 4-11.
@article{790704961b3349e198091cb3c23b1354,
title = "Godsil-McKay switching and isomorphism,",
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 sucient condition for being isomorphic after switching, and give examples which show that this condition is not necessary. For some graph products we obtain sucient conditions for being non-isomorphic after switching. As an example we nd that the tensor product of the grid L(';m) (' > m 2) and a graph with at least one vertex of degree two is not determined by its adjacency spectrum.",
author = "Aida Abiad and A.E. Brouwer and Haemers, {W. H.}",
year = "2015",
doi = "10.13001/1081-3810.2986",
language = "English",
volume = "28",
pages = "4--11",
journal = "Electronic Journal of Linear Algebra",
issn = "1081-3810",
publisher = "International Linear Algebra Society",

}

Godsil-McKay switching and isomorphism, / Abiad, Aida; Brouwer, A.E.; Haemers, W. H.

In: Electronic Journal of Linear Algebra, Vol. 28, 2015, p. 4-11.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Godsil-McKay switching and isomorphism,

AU - Abiad, Aida

AU - Brouwer, A.E.

AU - Haemers, W. H.

PY - 2015

Y1 - 2015

N2 - 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 sucient condition for being isomorphic after switching, and give examples which show that this condition is not necessary. For some graph products we obtain sucient conditions for being non-isomorphic after switching. As an example we nd that the tensor product of the grid L(';m) (' > m 2) and a graph with at least one vertex of degree two is not determined by its adjacency spectrum.

AB - 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 sucient condition for being isomorphic after switching, and give examples which show that this condition is not necessary. For some graph products we obtain sucient conditions for being non-isomorphic after switching. As an example we nd that the tensor product of the grid L(';m) (' > m 2) and a graph with at least one vertex of degree two is not determined by its adjacency spectrum.

U2 - 10.13001/1081-3810.2986

DO - 10.13001/1081-3810.2986

M3 - Article

VL - 28

SP - 4

EP - 11

JO - Electronic Journal of Linear Algebra

JF - Electronic Journal of Linear Algebra

SN - 1081-3810

ER -