GRAPHS WITH TWO MAIN AND TWO PLAIN EIGENVALUES

NEW

Problem: Reconstructed question: in finite simple undirected graphs, let $A$ be the adjacency matrix and $\mathbf j$ the all-one vector. For an eigenvalue $\theta$, let

$$p(\theta)=\dim(\ker(A-\theta I)\cap \mathbf j^\perp).$$

Then $\theta$ is main if $p(\theta)<\dim\ker(A-\theta I)$, and plain if $p(\theta)>0$. The refined spectrum records the main eigenvalues and the plain eigenvalues with their plain multiplicities. The question is: if two graphs have the same refined spectrum, must their complements be cospectral? This matches the terminology and Question 3.4 of the cited paper.

Result: No.

Let $G_1,G_2$ have vertex set $\{1,\dots,6\}$ and edge sets

$$E(G_1)=\{12,13,14,15,16,25,34\},$$ $$E(G_2)=\{13,14,16,23,24,25,34\}.$$

Both graphs are connected.

A direct determinant computation gives, for both adjacency matrices $A_i$,

$$\chi_{A_i}(x)=(x-1)(x+1)^2(x^3-x^2-5x+1).$$

Let $f(x)=x^3-x^2-5x+1$. Solving the eigenspaces gives

$$\ker(A_1-I)=\langle(0,1,-1,-1,1,0)\rangle,$$ $$\ker(A_1+I)=\langle(0,0,-1,1,0,0),(0,-1,0,0,1,0)\rangle,$$

and

$$\ker(A_2-I)=\langle(1,-1,0,0,-1,1)\rangle,$$ $$\ker(A_2+I)=\langle(0,0,-1,1,0,0),(-1,1,0,0,-1,1)\rangle.$$

All these vectors have coordinate sum $0$. Thus $1$ is plain with plain multiplicity $1$, and $-1$ is plain with plain multiplicity $2$, and neither is main.

For both graphs, the Krylov space generated by $\mathbf j$ has dimension $3$: explicitly,

$$\operatorname{rank}(\mathbf j,A_i\mathbf j,A_i^2\mathbf j)=3,$$

and direct multiplication gives $f(A_i)\mathbf j=0$. Hence the number of main eigenvalues is $3$. Since $1$ and $-1$ are not main, the three roots $\alpha,\beta,\gamma$ of $f$ are exactly the main eigenvalues.

Therefore both graphs have the same refined spectrum:

$$(3,2;\alpha,\beta,\gamma;[-1]^2,[1]^1).$$

However, their complements have characteristic polynomials

$$\chi_{\overline{G_1}}(x)=x^3(x+2)(x^2-2x-4),$$ $$\chi_{\overline{G_2}}(x)=x^2(x+2)(x^3-2x^2-4x+4).$$

These differ, for example in the multiplicity of the eigenvalue $0$. Hence $\overline{G_1}$ and $\overline{G_2}$ are not cospectral.

Thus the answer to the reconstructed question is negative, even for connected graphs.

Citation: Definitions and question: Sakander Hayat, Muhammad Javaid, Jack H. Koolen, “Graphs with two main and two plain eigenvalues,” arXiv:1612.00589, Section 3, Question 3.4. The counterexample above is explicit; no prior resolution is used.