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

screen-shot-2017-02-05-at-4-19-28-pm

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.

Thanks for reading!

Jonathan Gerhard

 

Advertisements

About jonathangerhard

I am a first-year PhD student in mathematics at the University of Michigan and I got my BS in mathematics in 2017 from James Madison University. I started this blog because I love math!
This entry was posted in 3D-Printing, MathematicalADD. Bookmark the permalink.

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

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

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

  3. Pingback: The Picture Post | Mathematical ADD

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s