Cocktail party and tripartite graphs are DS?

Question

Cocktail party graphs and $k_{n,n,n}$ (a tripartite graph) are 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. Does anyone know if there is a reference for this? Thanks to everyone for the help.

Answer 1

Yes, the cocktail party graphs and $K_{n,n,n}$ are determined by the spectra of their adjacency matrix. See for example, Proposition 6 of the paper Which graphs are determined by their spectrum? by van Dam and Haemers. Proposition 6 shows that the disjoint union of any collection of cliques is DS. You also need to use the fact that if $G$ is regular, than a graph is DS with respect to the adjacency matrix if and only if the complement of $G$ is DS with respect to the adjacency matrix. Since the cocktail party graphs and $K_{n,n,n}$ are both regular and the complement of a disjoint union of cliques, the result follows.

Since the paper appears to be behind a paywall, I will include a proof of Proposition 6 here.

Every graph which is the disjoint union of cliques is determined by the spectra of its adjacency matrix.

Proof. Let $G=K_{n_1} \sqcup \dots \sqcup K_{n_k}$ where $n_1 + \dots +n_k=n$. The spectra of $G$ is $n_1-1, \dots, n_k-1, -1, \dots, -1$, where $-1$ occurs $n-k$ times. Let $H$ be a graph with the same spectra and $A$ be the adjacency matrix of $H$. Since all eigenvalues of $A+I$ are nonnegative, $A+I$ is positive semidefinite. Therefore, $A+I=BB^T$ for some matrix $B$. Because the diagonal entries of $A+I$ are all $1$, each column of $B$ is a unit vector. Moreover, since $A+I$ is $0/1$-valued, it follows that if $x$ and $y$ are columns of $B$, then either $x=y$ or $x$ and $y$ are orthogonal. By grouping identical columns of $B$, we see that $A+I$ can be put in block diagonal form, where each block is an all-ones matrix. It follows that $H$ is also a disjoint union of cliques. Finally, it is easy to see that two graphs which are both the disjoint union of cliques have the same spectra if and only if they are isomorphic.