Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 4 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|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|improve this answer

Your Answer

 
discard

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.