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.
$\begingroup$
$\endgroup$
6
asked Nov 7, 2012 at 18:38
-
1$\begingroup$ I can't imagine any book on spectral graph theory that doesn't give this example. $\endgroup$– Dan PetersenNov 7, 2012 at 18:55
-
2$\begingroup$ 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? $\endgroup$– SuvritNov 7, 2012 at 18:56
-
$\begingroup$ @Suvrit: The OP's question is: what is the polynomial with those roots? $\endgroup$– Igor RivinNov 7, 2012 at 22:34
-
$\begingroup$ @Igor: So basically you / the OP don't want the polynomial in factorised form, but rather expanded out, with closed forms for the coefficients? $\endgroup$– SuvritNov 8, 2012 at 3:03
-
$\begingroup$ @Suvrit: I certainly do not want it, and am merely interpreting the OP's wishes. $\endgroup$– Igor RivinNov 8, 2012 at 4:26
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
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)$.
answered Nov 8, 2012 at 0:08