Last week I had a cold and could not do much thinking. So I spent my time making TikZ pictures for an upcoming talk of mine. This talk is on my recent work with Akihiro Munemasa on constructing cospectral strongly regular graphs. I think that the pictures are nice for a blog post, so here we go.

**1. The Spectrum of a Graph **

Two graphs and are called cospectral if their adjacency matrices and have the same eigenvalues. This is the same as saying that there is an orthogonal matrix with . Any permutation matrix is a valid choice for , but this is not very interesting as then and are isomorphic. Chris Godsil and Brendan McKay described one of the easiest interesting choices for in 1982. For a graph on vertices, a simplified version of their matrix is

Here is the all-ones matrix and is the identity matrix. Denote the first vertices of by and the remaining vertices by . Then is again the adjacency matrix of a graph if the following is satisfied:

- The induced subgraph on is regular.
- Every vertex in is adjacent to , or vertices of .

The new graph with adjacency matrix can be obtained from by modifying the edges of as follows:

- If has neighbours in , so , then .
- Otherwise, do not change the neighborhood of .

This is known as **Godsil-McKay (GM) switching**. A nice example for cospectral graphs, which I stole from Andries E. Brouwer’s homepage on strongly regular graphs, are the graph and the Shrikhande graph:

Both graphs have vertices, each vertex has neighbors, two adjacent vertices have neighbors in common as do two non-adjacent vertices. This implies that both graphs are cospectral (their spectrum is ). There many ways to see that these are not the same graphs, for example has cliques of size , while the Shrikhande graph does not.

We can identify a set , here in red, and obtain a new graph by applying GM switching:

It is maybe not obvious, but the second graph is again the Shrikhande graph. We can also compare the adjacency matrices, here the adjacency matrix of :

And here adjacency matrix after switching:

**2. A Second Switching **

Some time ago, I constructed new strongly regular graph with the same parameters as so-called collinearity graphs of polar spaces. This generalized work by Abiad and Haemers as well as Barwick, Jackson and Penttila, who both used Godsil-McKay switching. My construction was purely geometrical and very specific to the investigated graph. **It did not provide a general method** for obtaining cospectral graphs. My work with Akihiro Munemasa focused on amending this by finding the matrix that belongs to my old switching and finding a **general rule similar to Godsil-McKay switching** for obtaining cospectral graphs. We succeeded with this last September (in 2018), but it turned out that Wang, Qiu, and Hu already had a paper submitted at that time which described the same switching (which now appeared in Linear Algebra and its Applications). The matrix used this time is

A simplified description is as follows. We partition the vertices of into such that

- the induced subgraph on is -regular,
- the induced subgraph on is -regular,
- the induced subgraph on is -regular,
- each vertex satisfies or .

The new graph can be obtained from by modifying the edges as follows:

- If has , then .
- If has , then .
- Otherwise, do not change the neighborhood of .

Let’s call this **WQH switching**. Similar to Godsil-McKay switching, we can apply WQH switching to to obtain the Shrikhande graph. Here is in red and in blue.

This time, we had to change far fewer edges and the second graph looks prettier. For GM switching and WQH switching always yield isomorphic graphs, so we cannot actually obtain new graphs this way. The true usefulness of WQH switching comes for . Again, we can provide the adjacency matrices. Here for we have still have the following adjacency matrix:

And here for the Shrikhande graph:

WQH seems to become very useful for in geometric settings. Akihiro Munemasa and I used it to construct strongly regular graphs related to designs as well as polar spaces/orthogonality graphs. I also have nice pictures for that part, but no time to incorporate them into this post. You can read our preprint for more details. There is also much to be said about why people care about constructing new strongly regular graphs or cospectral graphs. The purpose of this post was to put my pictures somewhere and not explaining too much, so I might address this in the future.

Shouldn’t it be 1/m J_{2m} – I_m, instead of J_{2m} – 1/m I_m? In Godsil-McKay switching.

LikeLike

Yes, it has to be an orthogonal matrix. Thanks. I fixed this.

LikeLike

Hi, should this be corrected for WQH switching as well? I think you still need a 1/m before the J_m in the off-diagonal blocks of the matrix Q.

LikeLike

Of course. Thanks. Corrected it.

LikeLike