This Article is brought to you for free and open access by Wyoming Scholars Repository. It has been accepted for inclusion in Electronic Journal of Linear Algebra by an authorized editor of Wyoming Scholars Repository. For more information, please contact [email protected].

Recommended Citation Abiad, Aida; Brouwer, Andries E.; and Haemers, Willem H.. (2015), "Godsil-McKay switching and isomorphism", Electronic Journal of Linear Algebra, Volume 28. DOI: https://doi.org/10.13001/1081-3810.2986

http://repository.uwyo.edu/ela?utm_source=repository.uwyo.edu%2Fela%2Fvol28%2Fiss1%2F2&utm_medium=PDF&utm_campaign=PDFCoverPages

http://repository.uwyo.edu/ela/vol28?utm_source=repository.uwyo.edu%2Fela%2Fvol28%2Fiss1%2F2&utm_medium=PDF&utm_campaign=PDFCoverPages

http://repository.uwyo.edu/ela/vol28/iss1/2?utm_source=repository.uwyo.edu%2Fela%2Fvol28%2Fiss1%2F2&utm_medium=PDF&utm_campaign=PDFCoverPages

http://repository.uwyo.edu/ela?utm_source=repository.uwyo.edu%2Fela%2Fvol28%2Fiss1%2F2&utm_medium=PDF&utm_campaign=PDFCoverPages

https://doi.org/10.13001/1081-3810.2986

mailto:[email protected]

GODSIL-MCKAY SWITCHING AND ISOMORPHISM∗

AIDA ABIAD†, ANDRIES E. BROUWER‡, AND WILLEM H. HAEMERS∗

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 grid L(`, m) (` > m ≥ 2) and a graph with at least one vertex of degree two is not determined by its adjacency spectrum.

Key words. Godsil-McKay switching; Spectral characterization; Cospectral graphs; Graph

isomorphism; Graph products.

AMS subject classifications. 05C50

1. Introduction. An important activity in algebraic graph theory is to decide

if a graph is determined by the spectrum of the adjacency matrix (see the surveys

[2, 3]). Godsil-McKay switching is an operation on a graph that does not change the

spectrum, and provides a tool for disproving existence of such a characterization. For

this operation to work the graph needs a special structure. However, the presence

of this structure doesn’t imply that the graph is not determined by its spectrum;

it may be that after switching the graph is isomorphic to the original one. In this

note we investigate this phenomenon. We hoped to find some useful criteria for

isomorphism after switching. Unfortunately we found some strange examples, which

indicate that there is not much hope for such a criterium. Instead we obtain some

necessary conditions and show how they can be used to guarantee non-isomorphism

after switching for some graph products.

2. Godsil-McKay switching. Two graphs with the same (adjacency) spec-

trum are called cospectral. Godsil and McKay [5] introduced the following construc-

tion method for cospectral graphs.

Proposition 1. Let G be a graph and let {X1, . . . ,X`,Y} be a partition of the vertex set V (G) of G. Suppose that for every vertex x ∈ Y and every i ∈ {1, . . . ,`},

∗Received by the editors on June 27, 2014. Accepted for publication on August 11, 2014. Handling

Editor: Sebi Cioabă. †Tilburg University, Tilburg, The Netherlands ([email protected], [email protected]) ‡[email protected]

Godsil-McKay Switching and Isomorphism 5

x has either 0, 1 2 |Xi| or |Xi| neighbors in Xi. Moreover, suppose that for all i,j ∈

{1, . . . ,`} every vertex x ∈ Xi has the same number of neighbors in Xj. Make a new graph G′ as follows. For each x ∈ Y and i ∈ {1, . . . ,`} such that x has 1

2 |Xi|

neighbors in Xi delete the corresponding 1 2 |Xi| edges and join x instead to the 12|Xi|

other vertices in Xi. Then G and G ′ are cospectral.

The operation that changes G into G′ is called Godsil-McKay switching, and the

considered partition is a (Godsil-McKay) switching partition. In many applications

` = 1. Then the above condition requires that X = X1 induces a regular subgraph of

G, and that each vertex in Y has 0, 1 2 |X| or |X| neighbors in X. Such a set X will

be called a (Godsil-McKay) switching set. In this note we look for conditions on a

switching set under which G and G′ are isomorphic.

Let G be a graph with adjacency matrix A and switching set X. Let B be the

submatrix of A corresponding to X. Then

A =

[ B M

M >

] , with M =

[ N J O

] ,

where BJ = kJ for some k ∈ {0, . . . , |X| − 1}, and N > J = 1

2 |X|J. Note that not

every (but at least one) type of block N, J or O needs to be present. Let G′ be the

graph with adjacency matrix A′ obtained by Godsil-McKay switching with respect to

X in G. Then

A′ =

[ B M′

M′ >

] , with M′ =

[ J −N J O

] .

With the above notation, the following proposition is straightforward.

Proposition 2. If there exist permutation matrices P and Q such that PBP > =

B, PMQ > = M′ and QCQ

> = C, then G and G′ are isomorphic.

Any pair of vertices in G is a switching set, but such a set always satisfies the

above proposition, so switching produces isomorphic graphs. However, if |X| ≥ 4 then Proposition 2 is not automatically satisfied and Godsil-McKay switching usu-

ally (but not always) produces non-isomorphic graphs. To prove that G and G′ are

non-isomorphic it would help if the condition of Proposition 2 would also be neces-

sary for isomorphism. This however is not true! The isomorphism described in the

proposition fixes the switching set X (setwise). We shall see examples in the next

section where G and G′ are isomorphic, but no isomorphism fixes X. Because of these

examples it will be hard to find useful conditions for isomorphism that are necessary

and sufficient. Therefore we only present some easy sufficient conditions for being

non-isomorphic after Godsil-McKay switching. Let λG(x,y) denote the number of

common neighbors of two vertices x and y in G. It is clear that if the multiset of

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

degrees (i.e. {λG(x,x) |x ∈ V (G)}), or the multiset {λG(x,y) |x,y ∈ V (G)} changes after switching, then G and G′ are non-isomorphic. But we can be a bit more precise:

Lemma 3. The following conditions are sufficient for G and G′ being non-

isomorphic.

(i) The multiset of degrees (in G) of the vertices in X changes after switching.

(ii) The multiset ΛG = {λG(x,y) |x ∈ X,y ∈ V (G)} changes after switching. (iii) The vertices of X all have the same degree, and the multiset ΛG =

{λG(x,y) |x ∈ X,y ∈ Y} changes after switching.

Proof. (i) Clearly the degrees in Y don’t change by the switching, so the mul-

tiset of degrees of G changes whenever the degrees in X change. (ii) The multiset

{λG(x,y) |x,y ∈ Y} is not changed after switching, therefore {λG(x,y) |x,y ∈ V (G)} changes if ΛG(G) changes. (iii) If the vertices in X have the same degree, then

switching doesn’t change {λG(x,y) |x,y ∈ X}.

Suppose not all vertices in X have the same degree. Then in general the set

of degrees changes, and hence we get a non-isomorphic graph after switching. In

particular, it is easily verified that this is always the case if |X| = 4.

The conditions of Lemma 3 are not necessary for being non-isomorphic. There are

several examples of Godsil-McKay switching in a strongly regular graph G that gives

a non-isomorphic graph G′ (the smallest example is the 4 × 4 grid with a coclique X of size 4). However, G′ is also strongly regular with the same parameters as G (since

this property follows from the spectrum), and therefore ΛG = ΛG′ and ΛG = ΛG′ .

3. No isomorphism fixes the switching set. In this section we give examples

of graphs G with a switching set X for which the graphs G′ obtained by Godsil-McKay

switching are isomorphic with G, but where no isomorphism fixes X.

3.1. Regular tournaments. A (0, 1)-matrix T is a tournament matrix if T +

T> = J − I, and T is regular if all row (and column) sums are equal. If T has order m, then this row sum is (m− 1)/2, so m is odd.

Proposition 4. Let T be a regular tournament matrix of order m > 1, and

put N = T ⊗ J2 + I2m. Consider a regular graph H of order 2m with vertex set X and automorphism r that is a fixed-point-free involution, where the orbits of the

full automorphism group of H are the orbits of r. Let H have adjacency matrix B,

indexed such that r is represented by the permutation matrix R = Im ⊗ (J2 − I2). Construct a graph G on the union of two copies X1,X2 of X, with adjacency matrix

A =

[ B N

N >

] .

Godsil-McKay Switching and Isomorphism 7

Then G has Godsil-McKay switching set X1, and the switched graph G ′ is isomorphic

with G, whilst there is no isomorphism that fixes X1.

Proof. We have RN = J − N> and B = RBR>, and therefore A′ = QAQ>, where

Q =

[ O I

R O

] .

Thus G is isomorphic with G′. Suppose there is an isomorphism between G and

G′ that fixes the set X1 (and hence also X2). Then the isomorphism acts as an

automorphism on the subgraphs induced by X1 and X2, and hence fixes the orbits of

r on both copies of X. Since m > 1 this is impossible.

Regular tournament matrices are easily constructed for every odd order m. If E is

the adjacency matrix of an asymmetric regular graph (asymmetric means that the full

automorphism group is trivial), then E⊗J2 represents a graph whose automorphism group satisfies the condition of the proposition. An asymmetric regular graph exists

for every order at least 10 (see [1]), but also for m = 5, 7 and 9 graphs with the

required property do exist. For example when m = 5 we can take

B =

  Z O Z O J

O Z J Z O

Z J O Z O

O Z Z O J

J O O J O

  , and N =

 

I J J O O

O I J J O

O O I J J

J O O I J

J J O O I

  ,

where J = J2, I = I2 and Z = J2 − I2. So the construction works for every order 4m with m odd and at least 5. The smallest size of the switching set is 10. Since

in many applications the size of the switching set is 4, the question rises whether in

this special case the sufficient condition for isomorphism of Proposition 2 could be

necessary. Unfortunately this is again false, as is illustrated by the next example.

3.2. A switching set of size four. Let G be the bipartite graph on 12 + 6 = 18

vertices, where one part of the bipartition is {a,b,c,d,a′,b′,c′,d′,a′′,b′′,c′′,d′′}, the other is {ui | i ∈ Z/6Z}, and adjacencies are as follows:

u0 ∼a,b,a′,c′,a′′,d′′

u1 ∼b,c,a′,b′,a′′,c′′

u2 ∼b,d,b′,c′,a′′,b′′

u3 ∼c,d,b′,d′,b′′,c′′

u4 ∼a,d,c′,d′,b′′,d′′

u5 ∼a,c,a′,d′,c′′,d′′

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

Let the switching set be X = {a,b,c,d}. Then we have an isomorphism between G and the switched graph G′. Namely, φ : G → G′ given by φ(x) = x′, φ(x′) = x′′, φ(x′′) = x for x = a,b,c,d, and φ(ui) = ui+1 for i ∈ Z/6Z. We would like to show that there is no isomorphism fixing X (but there is). Put X′ = {a′,b′,c′,d′} and X′′ = {a′′,b′′,c′′,d′′} and U = {ui | i ∈ Z/6Z}. The graphs G and G′ are bipartite and connected, so any isomorphism ψ fixing X must also fix X′ ∪ X′′ and U. The triples ijk such that ui,uj,uk have a common neighbor in X are 045, 012, 135, 234,

and after switching 123, 345, 024, 015, so ψ must send the former triples to the latter.

The former triples are precisely the triples with a common neighbor in X′′, the latter

precisely those with a common neighbor in X′. So ψ must interchange X′ and X′′.

As it turns out, there is such a ψ, and we need to enlarge our graph to destroy this

unwanted isomorphism.

We can turn the 18-vertex non-example into a 21-vertex almost-example by

adding three vertices X, X′ and X′′, corresponding to the sets with the same names,

adjacent to their elements (thus: X∼a,b,c,d, etc.), and three directed edges X → X′, X′ → X′′, and X′′ → X. This gets rid of automorphisms ψ preserving X, but the example is directed. However, Frucht [4] showed that every finite group is the full

group of automorphisms of some finite undirected graph. In particular we can find

a graph with full group C3, the cyclic group of order 3, and use that instead of the

directed edges. This yields an actual example. Let us give an explicit example on 9

vertices ([6]). Take 9 vertices xi with x one of a,b,c and i ∈ Z/3Z. The 15 edges are aibi, aici−1, bici, bibi+1, bici−1. This yields a graph with C3 as full group of au-

tomorphisms. Identify the vertices X,X′,X′′ of the 21-vertex almost-example with

the vertices a0, a1 and a2 of this gadget (and remove the directed edges) to obtain a

27-vertex example as claimed.

4. Graph products. Consider graphs G and H with adjacency matrices A and

E, respectively. We recall that the tensor product of H and G, denoted by H × G is the graph with adjacency matrix E ⊗ A. We will also consider another product, which we will call the strengthened tensor product, defined by its adjacency matrix

(E + I) ⊗ A, and denoted by H ./ G. In terms of the graph, V (H × G) = V (H ./ G) = V (H)×V (G), the vertices (i,x) and (j,y) are adjacent in H×G if i is adjacent to j in H and x is adjacent to y in G, and the edges of H ./ G are those in H ×G together with {(i,x), (i,y)} with i ∈ V (H) and x adjacent to y in G. Notice that the strengthened tensor product H ./ G can be interpreted as a tensor product H × G were H is obtained from H by adding a loop at every vertex.

Let X be a switching set in G and suppose that one of the conditions of Lemma 3

is satisfied, so that G is non-isomorphic and cospectral with G′. Then it is easily

checked that also the products G×H and G ./ H are non-isomorphic and cospectral with G′×H and G′ ./ H, respectively. Indeed, non-isomorphism easily follows because

Godsil-McKay Switching and Isomorphism 9

λH×G((i,x), (j,y)) = λH (i,j)λG(x,y) and λH./G((i,x), (j,y)) = λH (i,j)λG(x,y),

therefore also the multisets {λH×G((i,x), (j,y)) |i,j ∈ V (H), x,y ∈ V (G)} and {λH./G((i,x), (j,y)) |i,j ∈ V (H), x,y ∈ V (G)} are changed after switching (assum- ing that H, resp. H, has at least one edge). Cospectrality follows from basic properties

of tensor products of matrices, but also from the observation that in both products

the sets {Xi = {i}×X}, with i ∈ V (H), together with the set Y of remaining vertices is a switching partition.

If none of the conditions of Lemma 3 is satisfied, so that it is conceivable that G

is isomorphic with G′, then under some easy conditions there exist switching sets in

H × G and H ./ G that lead to non-isomorphic graphs. For the formulation of the result we will use the notation of Section 2, and the notion of a pair of complementary

rows in a (0, 1)-matrix, which simply means that the sum of the two rows is equal to

the all-one row.

Theorem 5. Let G be a graph with a Godsil-McKay switching set X, such that

the vertices of X have the same degree, and suppose that ΛG = ΛG′ . Furthermore

suppose that either X is a coclique (i.e. B = O), N has at least two columns and

no pair of complementary rows, or that B has row sums 1 2 |X| and no pair of rows

of [ B N ] is complementary. Let H be a graph and let i be a vertex of H. Then the

subset {i}× X of V (H) × V (G) is a switching set in H × G as well as in H ./ G, and Godsil-McKay switching gives non-isomorphic cospectral graphs, provided that i

has degree at least 1 in case of the strengthened tensor product and i is adjacent to a

vertex of degree at least two in case of the tensor product.

Proof. It is easily checked that for both graph products, the set {i}× X is a switching set. We’ll apply Lemma 3(iii) and prove that the multisets ΛH×G and

ΛH./G change after switching.

First observe that the Kronecker products E⊗A and (E +I)⊗A consist of blocks matrices equal to A or O. After switching the blocks equal to A in the block row

and block column corresponding to i change, but the other blocks remain the same.

For the strengthened tensor product, the diagonal block corresponding to i becomes

the switched matrix A′. For both graph products the off-diagonal nonzero blocks in

block row i become A′′, which is obtained from A by switching with respect to the

rows corresponding to X. Note that we can obtain A′′ also from A′ by switching with

respect to the columns corresponding to X. From this it follows that A′′ > A′′ = A>A.

For convenience we restrict to the tensor product in the remainder of the proof; the

proof for the strengthened tensor product goes analogously. The multiset ΛH×G consists of the values λH×G((i,x), (j,y)) where (i,x) ∈{i}×X and (j,y) 6∈ {i}×X. We distinguish three cases.

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

Case (i): i = j. We have

{λH×G((i,x), (i,y)) |x ∈ X,y ∈ Y} = {λH (i, i)λG(x,y) |x ∈ X, y ∈ Y},

and A′A′ >

= A′′A′′ >

implies that

{λ(H×G)′ ((i,x), (i,y)) |x ∈ X,y ∈ Y} = {λH (i, i)λG′ (x,y) |x ∈ X, y ∈ Y}.

By assumption the multiset ΛG does not change after switching and therefore the

multiset {λH×G((i,x), (i,y)) |x ∈ X,y ∈ Y} is also invariant under switching.

Case (ii): i 6= j and y ∈ Y . For each j 6= i we have

{λ(H×G)′ ((i,x), (j,y)) |x ∈ X,y ∈ Y} = {λH (i,j)λG′ (x,y) |x ∈ X, y ∈ Y} =

{λH (i,j)λG(x,y) |x ∈ X, y ∈ Y} = {λH×G((i,x), (j,y)) |x ∈ X,y ∈ Y}.

Case (iii): i 6= j and x,y ∈ X. Choose ̂ 6= i such that λH (i, ̂) is maximal. It follows that λH (i, ̂) > 0 because i has a neighbor of degree at least two. (Note that for the

strengthened tensor product it suffices that the degree of i is at least 1.) We have

λH×G((i,x), (̂,x)) = λH (i, ̂)λG(x,x). After switching we get λ(H×G)′ ((i,x), (̂,x)) =

λH (i, ̂)µ(x), where µ(x) is the number of neighbors of x that remain a neighbor after

switching. Clearly µ(x) < λG(x,x), hence

λ(H×G)′ ((i,x), (̂,x)) < λH×G((i,x), (̂,x)).

For y 6= x we get λ(H×G)′ ((i,x), (j,y)) = λH (i,j)λG′ (x,y). Because the matrices N or [ B N ] which are switched to their complements have no complementary pair of

rows, it follows that λG′ (x,y) < λG(x,x). Hence we have

λ(H×G)′ ((i,x), (j,y)) < λH (i, ̂)λG(x,x) = λH×G((i,x), (̂,x)).

This implies that the number λH×G((i,x), (̂,x)) disappears at least once from the

multiset ΛH×G after switching.

In view of the previous section it seems relevant to remark that the proof of the

above theorem would have been much simpler if we could have used that there exists

an isomorphism that fixes the switching set.

The grid (or lattice graph) L(`,m) (which is the line graph of the complete bi-

partite graph K`.m) is determined by its spectrum, provided (`,m) 6= (4, 4). If ` ≥ 3, m ≥ 2 a 4-cycle in the grid is a switching set that satisfies the hypothesis of Theo- rem 5. Therefore the tensor product of L(`,m) (` ≥ 3, m ≥ 2) and a graph with at least one vertex of degree two is not determined by its adjacency spectrum

Godsil-McKay Switching and Isomorphism 11

The strengthened tensor product Kn ./ G (n > 1) is also known as a coclique

extension of G. So the above theorem gives some easy conditions for a coclique

extension to have non-isomorphic cospectral graphs. For example a coclique extension

of the grid L(`,m) with ` ≥ 3, m ≥ 2, is not determined by its spectrum.

Another example is the triangular graph T(m), which is the line graph of Km.

If m 6= 8 the spectrum determines T(m) and if m ≥ 4 a 4-cycle in T(m) satisfies the requirements of Theorem 5. Thus we can conclude that for m ≥ 4 a coclique extension of T(m) is not determined by its spectrum.

REFERENCES

[1] G. Baron, W. Imrich, Asymmetrische reguläre Graphen, Acta Math. Acad. Sci. Hungar. 20

(1969) 135–142.

[2] E. R. van Dam, W. H. Haemers, Which graphs are determined by their spectrum?, Linear Algebra

Appl. 373 (2003) 241–272.

[3] E. R. van Dam, W. H. Haemers, Developments on spectral characterizations of graphs, Discrete

Math. 309 (2009) 576–586.

[4] R. Frucht, Herstellung von Graphen mit vorgegebener abstrakter Gruppe, Compositio Math. 6

(1939) 239–250.

[5] C. D. Godsil, B. D. McKay, Constructing cospectral graphs, Aequationes Math. 25 (1982) 257–

268.

[6] G. Sabidussi, On the minimum order of graphs with a given automorphism group, Monatsh.

Math. 63 (1959) 124–127.

View publication statsView publication stats

https://www.researchgate.net/publication/263201042

Electronic Journal of Linear Algebra

2015

Godsil-McKay switching and isomorphism

Aida Abiad
Andries E. Brouwer
Willem H. Haemers

Recommended Citation

Godsil-McKay switching and isomorphism