## Visualizing the difference between the 4×4 Rook’s graph and the Shrikhande graph

In the summer of 2015, I did a research project characterizing the critical groups of the Rook’s graph and its complement. I won’t be talking much about that specific project here – instead, I just want to look at the structure of the Rook’s graph.

The $n \times m$ Rook’s graph is a specific type of chessboard graph. We take an $n \times m$ grid and put a vertex in each cell. We then connect a vertex $(x_1,y_1)$ to a vertex $(x_2, y_2)$ if you can get from the first to the second through a Rook’s move, i.e. if they are in the same row or column.

When $n = m$, the Rook’s graph is a strongly-regular graph with parameters $(n^2, 2n - 2, n - 2, 2)$. We denote this by $R_n$. This means it has $n^2$  vertices, each of degree $2n-2$. Additionally, any two adjacent vertices share $n-2$ neighbors (which comes from the fact that two adjacent vertices must be in the same row or column, and there must be $n-2$ other vertices in that row or column) and any two non-adjacent vertices share $2$ neighbors (if we draw a square with the two non-adjacent vertices at its corners, they will both be adjacent to the vertices lying at the other two corners).

For all $n \neq 4$, these parameters are uniquely satisfied by the $n \times n$ Rook’s graph. And yet, for $n = 4$, there is exactly one other non-isomorphic graph that satisfies the same parameters: The Shrikhande graph. We occasionally call this graph $S$.

So what goes wrong with $n = 4$? A nice way to distinguish $R_4$, the $4 \times 4$ Rook’s graph, and the Shirkhande graph is by the neighborhood of a vertex in each graph. The neighborhood of a vertex $v$ is the set of all vertices adjacent to it. We can look at the subgraph induced by the neighborhood of $v$ by removing all vertices not adjacent to $v$ and any edges adjacent to a vertex we removed.

The subgraph induced by the neighborhood of any vertex in $R_4$ is connected in two triangles (in other words, it looks like the wedge of two tetrahedra), while the subgraph induced by the neighborhood of any vertex in the Shrikhande graph is connected in a 6-cycle (so it looks like the cone of a hexagon).

I wanted to compare these graphs by laying out the Shrikhande graph in the same way that I did $R_4$, shown below The way I decided to do this was by using the algebraic definition of these two graphs. We can define the Shrikhande graph and the Rook’s graph as follows. We label the vertices of the grid with elements of $\mathbb{Z}/4\mathbb{Z} \times \mathbb{Z}/4\mathbb{Z}$ in the natural way, and connect two vertices if:

• (Rook’s graph) their difference lies in the set $\{\pm (0,1), \pm (1,0) , (2,0), (0,2) \}$.
• (Shrikhande graph) their difference lies in the set $\{ \pm (0,1), \pm (1,0),(1,1), (3,3)\}$.

This gives us a nice way to transition from the Rook’s graph, which we already have, and the Shrikhande graph. We simply remove all the edges whose difference is $(2,0)$ or $(0,2)$, and add in edges whose difference is $(1,1)$ or $(3,3)$.

Notice that both $R_4 \backslash S$ and $S \backslash R_4$ are isomorphic to the disjoint union of four $4$-cycles. Despite this, $(S \cap R_4) \cup (R_4 \backslash S) \ncong (S \cap R_4) \cup (S\backslash R_4),$

since the first is $R_4$ and the second is $S$. So what we see here is that graph homomorphisms don’t necessarily mesh well with unions of graphs. Of course, this isn’t too crazy of a thing, even something as simple as adding an edge to a graph can result in non-isomorphic graphs depending on the placement of the edges.

Anyways, we use this decomposition to put the Shrikhande graph together in a configuration similar to the Rook’s graph, and hope it prints well!

For a bit more fun, here is the Shrikhande graph and the Rook’s graph, created by putting together the pictures above.

Jonathan Gerhard 