Month: April 2019

Constructing Cospectral Graphs

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 {\Gamma} and {\overline{\Gamma}} are called cospectral if their adjacency matrices {A} and {\overline{A}} have the same eigenvalues. This is the same as saying that there is an orthogonal matrix {Q} with {\overline{A} = Q^T A Q}. Any permutation matrix is a valid choice for {Q}, but this is not very interesting as then {\Gamma} and {\overline{\Gamma}} are isomorphic. Chris Godsil and Brendan McKay described one of the easiest interesting choices for {Q} in 1982. For a graph {\Gamma} on {v} vertices, a simplified version of their matrix is

\displaystyle Q = \begin{pmatrix} \frac{1}{m} J_{2m} - I_{2m} & 0 \\ 0 & I_{v-2m} \end{pmatrix}.