GRAPHS WITH TWO MAIN AND TWO PLAIN EIGENVALUES

NEW

Problem: Reconstructed statement: let $\Gamma$ be a finite simple connected graph with adjacency matrix $A$. An eigenvalue is main if its eigenspace is not orthogonal to the all-ones vector ${\bf j}$, and plain if its eigenspace contains a nonzero vector orthogonal to ${\bf j}$. A graph is $t$-valenced if it has exactly $t$ distinct vertex degrees. With Seidel matrix $S=J-I-2A$, $\Gamma$ is strong if

$$S^{2}\in \operatorname{span}_{\mathbb R}\{S,I,J\}.$$

The conjecture asks for a universal positive integer $C$ such that every connected $t$-valenced graph with exactly two main and exactly two plain eigenvalues is strong whenever $t\ge C$.

Result: The conjecture is true. In fact one may take

$$C=3.$$

Proof. Let the two plain eigenvalues be $\theta,\tau$. Put ${\bf d}=A{\bf j}$, the degree vector.

Since $A$ has exactly two main eigenvalues, the $A$-cyclic space generated by ${\bf j}$ is two-dimensional. Hence

$$L:=\operatorname{span}\{{\bf j},{\bf d}\}$$

is $A$-invariant and has dimension $2$. Because $A$ is symmetric, $L^\perp$ is also $A$-invariant. Every eigenvector in $L^\perp$ is orthogonal to ${\bf j}$, so its eigenvalue is plain. Thus the restriction of $A$ to $L^\perp$ has only the eigenvalues $\theta,\tau$. Therefore

$$B:=(A-\theta I)(A-\tau I)$$

vanishes on $L^\perp$, and since $B$ is symmetric its image lies in $L$. Hence for some real $\alpha,\beta,\gamma$,

$$B=\alpha {\bf d}{\bf d}^{\top} +\beta({\bf d}{\bf j}^{\top}+{\bf j}{\bf d}^{\top}) +\gamma J .$$

Taking diagonal entries at a vertex $v$ of degree $k=d_v$, and using $A_{vv}=0$, $(A^2)_{vv}=k$, gives

$$k+\theta\tau=\alpha k^2+2\beta k+\gamma .$$

Thus every vertex degree is a root of the quadratic

$$\alpha x^2+(2\beta-1)x+(\gamma-\theta\tau).$$

If $\Gamma$ has at least three distinct degrees, this polynomial is identically zero. Hence

$$\alpha=0,\qquad \beta=\frac12,\qquad \gamma=\theta\tau,$$

so

$$(A-\theta I)(A-\tau I) =\frac12({\bf d}{\bf j}^{\top}+{\bf j}{\bf d}^{\top})+\theta\tau J.$$

Equivalently,

$$A^2=(\theta+\tau)A-\theta\tau I +\frac12({\bf d}{\bf j}^{\top}+{\bf j}{\bf d}^{\top}) +\theta\tau J.$$

Now compute

$$S^2=(J-I-2A)^2 =(n-2)J+I+4A+4A^2-2({\bf j}{\bf d}^{\top}+{\bf d}{\bf j}^{\top}).$$

Substituting the displayed formula for $A^2$, the mixed degree terms cancel, yielding

$$S^2= \bigl(n-2+4\theta\tau\bigr)J +\bigl(1-4\theta\tau\bigr)I +4(\theta+\tau+1)A.$$

Since $A=(J-I-S)/2$, this lies in $\operatorname{span}_{\mathbb R}\{S,I,J\}$. Therefore $\Gamma$ is strong.

Thus every connected $t$-valenced graph with two main and two plain eigenvalues is strong whenever $t\ge3$, proving the conjecture.

Verification audit: the proof uses exactly the paper’s definitions of $t$-valenced, main/plain eigenvalue, and strong graph. Connectedness is not strengthened; the argument only uses finite simple undirected adjacency matrices. The possibility that an eigenvalue is both main and plain is allowed. The conclusion is precisely the conjectured conclusion, with the explicit universal constant $C=3$.

Citation: Definitions and conjecture: Sakander Hayat, Muhammad Javaid, Jack H. Koolen, “Graphs with two main and two plain eigenvalues,” arXiv:1612.00589. The proof above is self-contained.