The Smith and Critical Groups of the Square Rook's Graph and its Complement

Joshua E. Ducey, Jonathan Gerhard, Noah Watson

Abstract


Let $R_{n}$ denote the graph with vertex set consisting of the squares of an $n \times n$ grid, with two squares of the grid adjacent when they lie in the same row or column.  This is the square rook's graph, and can also be thought of as the Cartesian product of two complete graphs of order $n$, or the line graph of the complete bipartite graph $K_{n,n}$.  In this paper we compute the Smith group and critical group of the graph $R_{n}$ and its complement.  This is equivalent to determining the Smith normal form of both the adjacency and Laplacian matrix of each of these graphs.  In doing so we verify a 1986 conjecture of Rushanan.

Keywords


Invariant factors; Elementary divisors; Smith normal form; Smith group; Critical group; Jacobian group; Sandpile group; Adjacency matrix; Cartesian product of graphs; Laplacian; Chip-firing; Line graph; Rook's graph

Full Text:

PDF