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

Abstract

A maximal minor $M$ of the Laplacian of an $n$-vertex Eulerian digraph $\Gamma$ gives rise to a finite group ${\mathbb{Z}}^{n-1}/{\mathbb{Z}}^{n-1}M$ known as the sandpile (or critical) group $S(\Gamma )$ of $\Gamma$. We determine $S(\Gamma )$ of the generalized de Bruijn graphs $\Gamma =\mathrm{DB}(n,d)$ with vertices $0,\dots ,n-1$ and arcs $(i,di+k)$ for $0\le i\le n-1$ and $0\le k\le 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\in {\mathrm{GL}}_n(p)$ we show that $S(\mathrm{DB}(n,p))$ is isomorphic to the quotient by $⟨X⟩$ of the centralizer of $X$ in ${\mathrm{PGL}}_n(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 ${\mathbb{F}}_{p^n}$ from spanning trees in $\mathrm{DB}(n,p)$.

I+24 pages

References in corpus (1)

• Automorphisms of necklaces and sandpile groups

Cited by in corpus (2)

• Automorphisms of necklaces and sandpile groups
• The sandpile group of a polygon flower