202308281126

type :Example tags : Algebraic Graph Theory

Spectrum of the complement of a graph

---

Question:

Let $G$ be a $k-regular$ connected graph and let $\overline{G}$ be the complement of $G$. Let the spectrum of $G$ be $k,{\theta }_2,\dots ,{\theta }_n$. Then the spectrum of $\overline{G}$ is $n-1-k,1-1{\theta }_2,\dots ,-1-{\theta }_n$.

Proof:

Let $A=A(G)$ Let $\overline{A}=A(\overline{G})$ then $\overline{A}=(J-I)-A$ hence

$$\begin{array}{rl}\bar{A}\vec{j}& =n\vec{j}-\vec{j}-A\vec{j}\\ & =(n-1)\vec{j}-k\vec{j}\\ & =(n-1-k)\vec{j}\end{array}$$

---

Related