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

MaRDI QIDQ727178zbMATHFDO

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)

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

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

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)

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.

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

Cites work

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

Cited in

(9)

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

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)