Complete bipartite graphs, DS graphs and interlacing theorem

Question

I want to prove $K_{n,n+1}$ is determined by the adjacency spectra, called DS graphs. I try to use theorem 1 of Esser and Harary. I suppose $tK_1+K_{p,q}$, $p\leq q$, has the same spectra with $K_{n,n+1}$, so $-\sqrt{n^2+n}$ is its negative eigenvalue. by interlacing theorem for complete multipartite graph (Theorem 1 of the paper) we have: $$p\leq \sqrt{n^2+n}\leq q.$$ so $$p^2\leq n^2+n=n(n+1)\leq q^2.$$ I think it's clear the only possible values for $p$ and $q$ are $n$ and $n+1$. But how can I prove this? Also, I have a question about theorem 1, is it correct $\lambda_{p-n+1}$ in first line of theorem? I think it's a typo and it's $\lambda_{p-n+2}$. Finally how can be deduced this theorem from Interlacing theorem? Thanks for the help.

Answer 1

Using the details of Esser and Harary's result is overkill. Once you have that any graph $G$ with the same spectrum as $K_{n,n+1}$ is $K_{p,q} \cup t K_1$, you do not need it for anything else.

The spectrum of $K_{n,n+1}$ tells you that $G$ must have $n(n+1)$ edges and $2n+1$ vertices; so $pq = n(n+1)$ and $p+q \le p+q+t = 2n+1$.

• If $p+q \le 2n$, then $pq$ is maximized at $n^2$ by taking $p=q=n$, and $n^2 < n(n+1)$, so this case doesn't work at all.
• If $p+q = 2n+1$ and $pq = n(n+1)$, we solve a quadratic equation to find that $\{p,q\} = \{n,n+1\}$.