  We determine the critical groups of the generalized de Bruijn graphs
DB$(n,d)$ and generalized Kautz graphs Kautz$(n,d)$, thus extending and
completing earlier results for the classical de Bruijn and Kautz graphs.
Moreover, for a prime $p$ the critical groups of DB$(n,p)$ are shown to be in
close correspondence with groups of $n\times n$ circulant matrices over
$\mathbb{F}_p$, which explains numerical data in [OEIS:A027362], and suggests
the possibility to construct normal bases in $\mathbb{F}_{p^n}$ from spanning
trees in DB$(n,p)$.
