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 Rook’s graph is a specific type of chessboard graph. We take an grid and put a vertex in each cell. We then connect a vertex to a vertex 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 , the Rook’s graph is a strongly-regular graph with parameters . We denote this by . This means it has vertices, each of degree . Additionally, any two adjacent vertices share neighbors (which comes from the fact that two adjacent vertices must be in the same row or column, and there must be other vertices in that row or column) and any two non-adjacent vertices share 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 , these parameters are uniquely satisfied by the Rook’s graph. And yet, for , there is exactly one other non-isomorphic graph that satisfies the same parameters: The Shrikhande graph. We occasionally call this graph .
So what goes wrong with ? A nice way to distinguish , the Rook’s graph, and the Shirkhande graph is by the neighborhood of a vertex in each graph. The neighborhood of a vertex is the set of all vertices adjacent to it. We can look at the subgraph induced by the neighborhood of by removing all vertices not adjacent to and any edges adjacent to a vertex we removed.
The subgraph induced by the neighborhood of any vertex in 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 , 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 in the natural way, and connect two vertices if:
- (Rook’s graph) their difference lies in the set .
- (Shrikhande graph) their difference lies in the set .
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 or , and add in edges whose difference is or .
Notice that both and are isomorphic to the disjoint union of four -cycles. Despite this,
since the first is and the second is . 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.
Thanks for reading!