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

  • Joshua E. Ducey
  • Jonathan Gerhard
  • Noah Watson
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


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.
Article Number