Some tripartite graphs and DS graphs.

Question

I know $K_{n,n,n}$ is determined by its adjacency spectrum (by using its regularity) and I know complete multipartite graphs are not determined by their adjacency spectra, in general. What about $K_{1,n,n}$ and $K_{1,1,n}$ (complete tripartite graphs)? are they determined by the spectra of their adjacency matrices? I think thay are DS ( determined by the adjacency spectrum) but I can't find a reference for that or prove it. Does anyone know if there is a reference for this? Or a refrence for complete tripartite graphs? Thanks to everyone for the help.

Answer 1

From the spectrum of $K_{1,n,n}$ or $K_{1,1,n}$, we can determine:

• That a graph with that spectrum is a complete multipartite graph, possibly with isolated vertices added. (Such graphs are the only ones with exactly one positive eigenvalue; see, e.g., this question.)
• That in fact the complete multipartite component is a tripartite graph $K_{a,b,c}$, by the count of nonzero eigenvalues. (The isolated vertices will only add some number of $0$ eigenvalues.)
• We also know that $ab+ac+bc$, the number of edges of the $K_{a,b,c}$ component, must match the number of edges in $K_{1,n,n}$ or $K_{1,1,n}$ respectively. The edge count is determined by the eigenvalues.

Esser and Harary's On the spectrum of a complete multipartite graph tells us more: the negative eigenvalues of $K_{a,b,c}$ with $a \le b \le c$ are $\lambda_{a+b+c-1} \in [-b,-a]$ and $\lambda_{a+b+c} \in [-c,-b]$. They also give some guarantees on strictness, of which we only need one: if $a < b$, then $\lambda_{a+b+c-1} \in (-b,-a)$.

This is enough to deal with $K_{1,1,n}$, which has an eigenvalue of $-1$. For $K_{a,b,c}$ to have an eigenvalue of $-1$, we must have $a=1$ (since $\lambda_{a+b+c-1} \le -a$) and $b=1$ (or else $\lambda_{a+b+c-1} < a$). But no $K_{1,1,c}$ with $c \ne n$ has the same number of edges as $K_{1,1,n}$.

For $K_{1,n,n}$, we get a negative eigenvalue of $\frac{n - \sqrt{n^2+8n}}{2} \in (-2,-1]$, so any potential cospectral mate with a tripartite component of $K_{a,b,c}$ must have $a=1$, too. Also, the number of edges must match $K_{1,n,n}$: $b + c + bc = 2n + n^2$, or $(b+1)(c+1) = (n+1)^2$. But from this, it follows that $b+c\ge 2n$, with equality only if $b=c=n$, so any other tripartite graph $K_{1,b,c}$ with $2n+n^2$ edges has more vertices than $K_{1,n,n}$.

---

In fact, cospectral mates of complete tripartite graphs are pretty rare. The smallest example I found was $K_{5,6,20}$, which has the same spectrum as $K_{4,10,15} \cup 2K_1$. They do exist, though :)

Another approach to the problem, once we've figured out that we're looking for something of the form $K_{a,b,c} \cup d K_1$, is to compute the characteristic polynomial: it is $$ \pm x^{a+b+c+d-3}(x^3 - (ab + ac + bc)x - 2abc). $$ So $K_{a,b,c}$ and $K_{a',b',c'}$ are "cospectral up to isolated vertices" iff $ab + ac + bc = a'b' + a'c' + b'c'$ and $abc = a'b'c'$.