Determine all graphs with characteristic polynomial $t^8-24t^6-64t^5-48t^4$

Question

Determine all graphs with characteristic polynomial $t^8-24t^6-64t^5-48t^4$.

Let $A$ be the adjacent matrix of the graph $G$.

Since $t^8-24t^6-64t^5-48t^4 = t^4(t-6)(t+2)^3$, $$\text{spec}(A) = \begin{pmatrix} 6 & 0 & -2 \\ 1 & 4 & 3 \end{pmatrix}.$$

Is there any way to determine $G$ by the spectrum of $A$?

Answer 1

The first obvious thing to notice is that the graph has 8 vertices as the characteristic polynomial is of degree 8.

Secondly, the graph has 24 edges due to the degree 6 term. To see this, suppose that $\pi$ is a permutation of $[8]$ which contributes to the $t^6$ term. Since the diagonal entries of $A-tI$ are all $-t$, $\pi=(ij)$ for some $i\neq j$. Then $\pi$ contributes a non-zero value iff $ij$ is an edge of the graph. Furthermore, all of these permutations have the same sign, so you know there's no cancellation. Hence, $G$ must have 24 edges.

We can do a similar analysis for the $t^5$ term. If $\pi$ is a permutation that contributes to this term, then it has exactly $5$ fixed points, so $\pi=(ijk)$ for some $i\neq j\neq k$. By similar reasoning as above, we know that $G$ has 32 triangles (32 instead of 64 since each triangle is counted twice).

Next, for the $t^4$ term. A permutation contributing here either has the form $(ij)(k\ell)$ or $(ijk\ell)$. The $(ijk\ell)$ terms count copies of $C_4$ (again, each one is counted twice) and the $(ij)(k\ell)$ terms count pairs of disjoint edges (each pair is only counted once here). The caveat here is that these permutations have opposite signs, so you need to take that into account.

Continuing in this fashion, you can get a relations between various other cycle types.

I know this doesn't completely answer your question, but maybe you can get enough information so that an exhaustive search with naughty won't take too long.

Edit: After I wrote this, I realized that the fact that the graph has 24 edges restricts things a lot as a graph on 8 vertices has at most 28 edges. My guess is that the graph must be the complement of a perfect matching since this graph also has the correct number of triangles.