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) $$
Best Answer
Jesus revealed this answer to me the following for the second part
I supply the answer for part two
the Let $x_i$ be the eigenvalue of $X$, then $$\Phi (X, x)=\displaystyle \prod _{i=1} ^{n} (x-x_i)= (x-x_1)\prod _{i=2} ^{n} (x-x_i) = (x-k)\prod _{i=2} ^{n} (x-x_i)$$ It follows from this that $$\Phi (X, -x-1)=\displaystyle (-x-k-1)\prod _{i=2} ^{n} (-x-1- \theta _i)$$ Similarly we calculate \begin{align*} \Phi (\overline{X}, x) &=\displaystyle \prod _{i=1} ^{n} (x-x_i)\\ &= (x-x_1)\prod _{i=2} ^{n} (x-x_i)\\ &= (x-(n-k-1))\prod _{i=2} ^{n} (x-(-1-\theta _i))\\ &= (x-n+k+1) \prod _{i=2}^{n}(x+1+\theta_i)\\ &= (x-n+k+1) \frac{n+k+1}{n+k+1} \prod _{i=2}^{n}(x+1+\theta_i)\\ &= (x-n+k+1) \frac{n+k+1}{n+k+1} \left( -1 \right) ^{n-1} \prod _{i=2}^{n}(-x-1-\theta_i)\\ &= \left( -1 \right) ^{n} \frac{n+k+1}{x-n+k+1} (-x-k-1) \prod _{i=2}^{n}(-x-1-\theta_i)\\ &= \left( -1 \right) ^{n} \frac{n+k+1}{x-n+k+1} \Phi (X, -x-1) \end{align*}\\ Hence we can write $\displaystyle \Phi (\overline{X}, x)= \left( -1 \right) ^{n} \frac{n+k+1}{x-n+k+1} \Phi (X, -x-1) $second part