Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields

Journal article

A maximal minor M of the Laplacian of an n-vertex Eulerian digraph Γ gives rise to a finite group Zn−1/Zn−1M known as the sandpile (or critical) group S(Γ) of Γ. We determine S(Γ) of the generalized de Bruijn graphs Γ = DB(n, d) with vertices 0, ..., n − 1 and arcs (i, di + k) for 0 ≤ i ≤ n − 1 and 0 ≤ k ≤ d − 1, and closely related generalized Kautz graphs, extending and completing earlier results for the classical de Bruijn and Kautz graphs.

Moreover, for a prime p and an n-cycle permutation matrix X ∈ GLn(p) we show that S(DB(n, p)) is isomorphic to the quotient by (X) of the centralizer of X in PGLn(p). This offers an explanation for the coincidence of numerical data in sequences A027362 and A003473 of the OEIS, and allows one to speculate upon a possibility to construct normal bases in the finite field Fpn from spanning trees in DB(n, p).

Authors: Chan, SH; Hollmann, HDL; Pasechnik, DV

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Journal of Algebra
• Volume: 421
• Pages: 268–295
• Publication date: 2014-09-12
• DOI: 10.1016/j.jalgebra.2014.08.029
• ISSN: 0021-8693
• Language: English
• Keywords: sandpile groups; generalized de Bruijn and Kautz graphs; invertible circulants