Spectrum of cycle graph with edges replaced by triangles I'm interested in the following question. Start with a cycle $C_n$. Now, add $n$ more vertices, each of them connected to a different pair of adjacent vertices in the cycle. I think this is sometimes called the semitotal graph of the cycle, but I can't find the spectrum anywhere. Anyway, I want to find the eigenvalues of the adjacency matrix.
Here's what I have so far. The graph has $n$ vertices of degree 4 (the original vertices of the cycle, which I'll call the "original vertices"), and $n$ vertices of degree 2 (the vertices added, which I'll call the "points"). Let's look first for eigenfunctions which are constant on the original vertices and on the points. Let's assume the constants are nonzero, so normalize so that on the points it's equal to 1, and on the original vertices say it's equal to $b$. When we hit it with the adjacency matrix, we get the equations
$$
2b+2 = \lambda b  \qquad 2b = \lambda
$$
by examining the original vertices and the points separately. This leads to $b^2 - b -1 = 0$, from which $b = \frac{1 \pm \sqrt{5}}{2}$ and $\lambda = 1 \pm \sqrt{5}$. OK, so that's 2 eigenvalues out of the way, $2n-2$ more to go, and I believe $1 + \sqrt{5}$ would be the P-F one. Now I get a bit stumped. If $n$ is even, then we could put 0's at all the points, then alternate $1$'s and $-1$'s around the cycle, and this would lead to an eigenvalue of $-2$, and similarly we can alternate $1$'s and $-1$'s around the points and put zeroes at the original points, and this gives $0$ as an eigenvalue. However these don't work if $n$ is odd, and in any case we are still missing many eigenvalues. Any suggestions?
Greg
 A: Well, you know the eigenvectors for $C_n$: take an $n^{\text{th}}$ root of unity $\omega$, and assign $\omega^i$ to the $i^{\text{th}}$ vertex around the cycle.
We can try extending each of these to an eigenvector of your graph. If this works out, then the point between the $i^{\text{th}}$ and $(i+1)^{\text{th}}$ original vertex must be assigned the value $\lambda^{-1}(\omega^i + \omega^{i+1})$, where $\lambda$ is the eigenvalue. If this happens, the $i^{\text{th}}$ original vertex goes from $\omega^i$ to
$$
   \omega^{i-1} + \omega^{i+1} + \lambda^{-1}(\omega^{i-1} + \omega^i) + \lambda^{-1}(\omega^i + \omega^{i+1})
$$
and we would like this to be equal to $\lambda \omega^i$. Simplifying, we get
$$
   \omega^{-1} + \omega + \lambda^{-1}(\omega^{-1} + 2 + \omega) = \lambda 
$$
which is a quadratic equation in $\lambda$. So for each $n^{\text{th}}$ root of unity, we get two extensions of the corresponding eigenvector of $C_n$. (An exception is when $\omega = -1$, when we get a linear equation. But you've already found the missing eigenvector in that case: it's the one with all the original vertices set to $0$.)
In fact, this is the same idea you started with, except you only applied it in the case $\omega = 1$.
