Lamplighter groups, de Bruijn graphs, spider-web graphs and their spectra

Abstract

We describe the infinite family of spider-web graphs $S_{k,M,N}$, $k\ge 2$, $M\ge 1$ and $N\ge 0$, studied in physical literature as tensor products of well-known de Brujin graphs $B_{k,N}$ and cyclic graphs $C_M$ and show that these graphs are Schreier graphs of the lamplighter groups $L_k=Z/kZ\wr Z$. This allows us to compute their spectra and to identify the infinite limit of $S_{k,M,N}$, as $N,M\to \infty$, with the Cayley graph of the lamplighter group $L_k$. This is the final version of the article, taking in account comments from the referees and with an extended introduction.

37 pages, 10 figures