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!

Jonathan Gerhard

Pingback: My 3D Printing Project – A Summary | Mathematical ADD

Pingback: 3D Printing Graphs, Knots, and…Books? | Mathematical ADD

Pingback: The Picture Post | Mathematical ADD

Pingback: Shapeways Education Grant Stories: Jonathan Gerhard’s 3D Printed Visualizations of Topological Homotopies - Shapeways Magazine

Pingback: 如何设计局部的、计算效率高的、可证明的图神经网络？ - KKNEWS

Pingback: Weisfeiler-Lehman: Using Substructures For Provably Expressive GNN

Hello! Fantastic post, thank you for sharing this in such helpful detail. After reading this many, many times, I have just noticed one thing that I think is an error:

(Shrikhande graph) their difference lies in the set { \pm (0,1), \pm (1,0),(1,1), (3,3)}.

I believe those final two terms should actually be (1,3) and (3,1), NOT (1,1) and (3,3).

Looking at the image on the right just below that (showing the edges in S \ R4), I see edges of the form “over 1 and up 3” (like an elongated Knight’s move), as opposed to “over 3 and up 3”.

LikeLike

Hi again! After looking that over more carefully, I realize this may just be a difference of perspective. I was looking at the origin (0,0) being the bottom-left, and (1,1) meaning “right 1, up 1.”

But, I see now that you are interpreting the origin (0,0) as the top-left, and (1,1) meaning “right 1, down 1.”

Sorry for the confusion 🙂

LikeLike