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.


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.

  • $\begingroup$ Great. Thanks for your answer. You mean since these graphs are regular, we can take $\overline{A}$, instead of A, the adjacency matrix, it's right? $\endgroup$ – N math Feb 14 at 9:54
  • $\begingroup$ Yes, that's correct. $\endgroup$ – Tony Huynh Feb 14 at 10:57
  • $\begingroup$ Thanks for your answer. $\endgroup$ – N math Feb 14 at 12:54
  • 1
    $\begingroup$ You're welcome. I also added a proof of Proposition 6 here. If you are satisfied with the answer, you can click on the green check mark to show that it has been answered. $\endgroup$ – Tony Huynh Feb 15 at 8:09
  • $\begingroup$ A tiny bit is missing in order to go to the complement. Namely, a regular graph cannot be cospectral to an irregular graph. This is an old result of Sachs: a graph is regular iff the sum of the squares of the eigenvalues equal $n$ times the largest eigenvalue. $\endgroup$ – Brendan McKay Feb 15 at 10:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.