On the spectra of wreath products of circulant graphs (Q6601245)

The authors consider the wreath product of graphs, which is defined in such a way that the wreath product of the Cayley graphs of two finite groups is the Cayley graph of the wreath products of these groups. Specifically, the wreath product \(G_1\wr G_2\) of two graphs \(G_1=(V_1,E_1)\) with \(|V_1|=\{u_1,\dots,u_n\}\) and \(G_2=(V_2,E_2)\) is defined so that the vertex set of \(G_1\wr G_2\) is the set \(V_2^{V_1}\times V_1=\{(v_1,\dots,v_n)u_i: v_j\in V_2, u_i\in V_1\}\) with two vertices \((v_1,\dots,v_n)u_i\) and \((v^\prime_1,\dots,v^\prime_n)u_{i^\prime}\) adjacent in \(G_1\wr G_2\) if either (edges of type I): \(i=i^\prime\) and \(v_j=v^\prime_j\) for every \(j\neq i\) and \((v_i,v^\prime_i)\in E_2\) or (edges of type II): \(v_j=v^\prime_j\) for every \(1\leq j\leq n\) and \((u_i,u_{i^\prime})\in E_1\).\N\NIn Theorems 2.3 and 2.4, the authors characterize the adjacency spectrum of the wreath product of a complete graph and a circulant graph, which is a Cayley graph on a cyclic group. As an illustration of these theorems, they apply them to special cases when the circulant graph is either the Möbius ladder, the complete bipartite graph \(K_{m,m}\) without a perfect matching, or the Andrásfai graph.