Welcome to MathOverflow

Question

0

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.

edited Nov 8 at 1:25

Gerry Myerson
15.6k●1●47●87

asked Nov 7 at 18:38

Feldmann Denis
1,768●2●15

1

I can't imagine any book on spectral graph theory that doesn't give this example. – Dan Petersen Nov 7 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? – S. Sra Nov 7 at 18:56

@Suvrit: The OP's question is: what is the polynomial with those roots? – Igor Rivin Nov 7 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? – S. Sra Nov 8 at 3:03

@Suvrit: I certainly do not want it, and am merely interpreting the OP's wishes. – Igor Rivin Nov 8 at 4:26

show 1 more comment

Chris Godsil · Accepted Answer · 2012-11-08 00:08:13Z UTC

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

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.