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

We study the infinite family of spider-web graphs {S-k,S-N,S-M}, k >= 2, N >= 0 and M >= 1, initiated in the 50s in the context of network theory. It was later shown in physical literature that these graphs have remarkable percolation and spectral properties. We provide a mathematical explanation of these properties by putting the spider-web graphs in the context of group theory and algebraic graph theory. Namely, we realize them as tensor products of the well-known de Bruijn graphs {B-k,B-N} with cyclic graphs {C-M} and show that these graphs are described by the action of the lamplighter group L-k = Z/kZZ on the infinite binary tree. Our main result is the identification of the infinite limit of {S-k,S-N,S-M}, as N, M -> infinity, with the Cayley graph of the lamplighter group L-k which, in turn, is one of the famous Diestel-Leader graphs DLk,k. As an application we compute the spectra of all spider-web graphs and show their convergence to the discrete spectral distribution associated with the Laplacian on the lamplighter group.