Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
up vote 5 down vote accepted

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.)

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.