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) $$
$\endgroup$ 31 Answer
$\begingroup$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
$\endgroup$
