Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is there a closed form for the characteristic polynomial of the graph cycle (of $n$ edges and $n$ summits)?

I know it for the graph path (it is a Chebyschev polynomial), but I couldn't find a closed form when adding the missing edge.

share|improve this question
1  
I can't imagine any book on spectral graph theory that doesn't give this example. –  Dan Petersen Nov 7 '12 at 18:55
2  
maybe i am misunderstanding something; a graph cycle has a circulant matrix as its adjacency matrix, with eigenvalues $2\cos(2\pi k/n)$, where $k=0,1,\ldots,n-1$, for the cycle $C_n$. So the char poly is fully determined. Maybe the OP means something else? –  Suvrit Nov 7 '12 at 18:56
    
@Suvrit: The OP's question is: what is the polynomial with those roots? –  Igor Rivin Nov 7 '12 at 22:34
    
@Igor: So basically you / the OP don't want the polynomial in factorised form, but rather expanded out, with closed forms for the coefficients? –  Suvrit Nov 8 '12 at 3:03
    
@Suvrit: I certainly do not want it, and am merely interpreting the OP's wishes. –  Igor Rivin Nov 8 '12 at 4:26
show 1 more comment

1 Answer

up vote 3 down vote accepted

If I use $\phi$ for characteristic polynomial, then $$ \phi(C_n,t) = \phi(P_n,t) - \phi(P_{n-2},t) - 2. $$ This follows from the formulas in Section 4.1 of "Algebraic Combinatorics" by yours truly, see in particular Exercise 5 in Chapter 4. (Sorry about the self-referencing, but I have no recollection of seeing the formula elsewhere.) Since the coefficient of $t^{n-2r}$ in $\phi(P_n,t)$ is $(-1)^r\binom{n-r}{r}$, the above identity leads to a simple expression for the coefficients of $\phi(C_n,t)$.

share|improve this answer
add comment

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.