Spectrum of a 3-regular graph

Question

Let $D_n$ be the following graph on $2n$ vertices: $V=\mathbb{Z}_n\times\{0,1\}$ and $E=\{(i,j)(i+1,j): i\in \mathbb{Z}_n,j\in \{0,1\}\}\cup\{(i,0)(i,1):i\in\mathbb{Z}_n\}$. What is the spectrum of $D_n$?

It is clear to me that any vertex $(i,j)$ is adjacent only to $(i+1,j)$, $(i-1,j)$ and $(i,(j+1)mod2)$ and hence such a graph is $3$-regular (except for the case of $n=2$). How do I proceed from this point to compute the spectrum?

Additionally I know that all eigenvalues are $\le 3$ in modulus, $3$ is an eigenvalue of multiplicity 1 as the graph is connected.

Any hint or information about this graph will also be appreciated.

Thanks

Answer 1

Your graph is the Cartesian product of the cycle $C_n$ and the complete graph $K_2$. So its adjacency matrix is $$ A(C_n) \otimes I +I \otimes A(K_2) $$ and hence its eigenvalues are the numbers $\theta\pm1$, where $\theta$ runs over the eigenvalues of the cycle. (Here $\otimes$ is the Kronecker product of matrices.)

Answer 2

You can consider this as two cycles with cross-connections. The cycles would independently have the Fourier modes as eigenmodes. Applying the adjacency matrix to a linear combination of two Fourier modes of the same frequency for the two cycles again yields such a linear combination, so the space decomposes into two-dimensional eigenspaces in which you can separately diagonalize the adjacency matrix.