I have 2 questions about how to find the characteristic polynomial of some graphs.
- If G is a simple cycle with n vertices and n edges, $C_n$, I need to find the characteristic polynomial of $C_n$ (the characteristic polynomial of the adjacency matrix).
I tryed to find some reccursive equation to the characteristic polynomial of the adjacency matrix:
$$ \begin{pmatrix} 0 & 1 & 0 & & \cdots & 0 & 1 \\ 1 & 0 & 1 & 0 & \cdots & 0 & 0\\ 0 & 1 & 0 & 1 & 0 & \cdots & 0 \\ \vdots && \ddots & \ddots& \ddots& \ddots \\ 0 && &&&&1\\ 1 &0&&&0&1&0\\ \end{pmatrix} $$
but I didn't succeed.
\2. I have a graph G that is k-regular, and I need to prove a connection between characteristic polynomials of G and G complement, $\overline G$: $$ p_\overline G(x) = (-1)^n{x-n+k+1\over x+k+1}p_G(-x-1) $$