The Smith and critical groups of the square rook's graph and its complement

zbMATH Open1351.05105arXiv1507.06583MaRDI QIDQ727178FDOQ727178

Authors: Joshua E. Ducey, Jonathan Gerhard, Noah Watson 

Publication date: 6 December 2016

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Let $R_n$ denote the graph with vertex set consisting of the squares of an $nimesn$ 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.

Full work available at URL: https://arxiv.org/abs/1507.06583

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• The Smith and critical groups of Paley graphs
• The Smith group of the hypercube graph
• The critical group of the Kneser graph on 2-subsets of an \(n\)-element set
• Smith forms for adjacency matrices of circulant graphs
• On the critical group of the \(n\)-cube

zbMATH Keywords

adjacency matrixLaplacianline graphCartesian product of graphscritical groupSmith normal formsandpile groupelementary divisorschip-firinginvariant factorsJacobian grouprook's graphSmith group

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Spectra of graphs
• Chip-firing and the critical group of a graph
• Smith normal form and Laplacians
• On the \(p\)-rank of the adjacency matrices of strongly regular graphs
• A finite group attached to the laplacian of a graph
• A diagonal form for the incidence matrices of \(t\)-subsets vs. \(k\)- subsets
• The Uniqueness of the $\mathrm{L}_2$ Association Scheme
• Smith normal forms of incidence matrices
• A short proof of Gamas's theorem
• On the Line-Graph of the Complete Bigraph

Cited In (9)

• Digraphs with at most one trivial critical ideal
• The Smith group of the hypercube graph
• Critical group structure from the parameters of a strongly regular graph
• Graphs with few trivial characteristic ideals
• Critical groups of Van Lint-Schrijver cyclotomic strongly regular graphs
• Sandpile groups for cones over trees
• Difference families, skew Hadamard matrices, and critical groups of doubly regular tournaments
• Critical groups of strongly regular graphs and their generalizations
• Chip-firing games and critical groups

This page was built for publication: The Smith and critical groups of the square rook's graph and its complement

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q727178)