GRAPHS WITH AT MOST FOUR SEIDEL EIGENVALUES

NEW

Problem: Let $G$ be a finite simple graph of order $n\ge 6$. Its Seidel matrix is

Two graphs are Seidel equivalent if their Seidel matrices are related by $S\mapsto DSD$ for some diagonal $\{\pm1\}$-matrix $D$.

I reconstruct $G\in G_3(n,n-3)$ as meaning that $S(G)$ has four Seidel eigenvalues

with $\alpha$ of multiplicity $n-3$ and the other three simple. The notation and the displayed inequalities in the conjecture support this.

The order condition for $K_{i,j}\cup \overline K_p$ is necessarily $i+j+p=n$; the printed inequality $p\le n-(i+j)$ is interpreted with this implicit equality.

Result: The conjecture is true under this natural reconstruction.

Proof. Suppose first

Ordering the eigenvalues gives

For any $4\times4$ principal Seidel submatrix $T$, Cauchy interlacing gives

hence $\mu_2(T)=\alpha$.

Every $4\times4$ Seidel matrix, after switching, has first row all $1$’s and is one of the three spectral types

Thus its second-smallest eigenvalue is either $-1$ or $1$. Since $\alpha<0$, necessarily

Therefore $S(G)+I$ has rank $3$.

Now switch $G$ so that the first row of $M:=S(G)+I$ is all $1$’s. Then $M=J-2A$, where $A$ is the adjacency matrix of a graph $F$ with vertex $1$ isolated. Since $\operatorname{rank}M=3$, all neighborhood vectors of $F$ lie in a two-dimensional subspace after subtracting the all-one row. Hence there are at most four distinct neighborhood types. One type is the zero type, consisting of isolated vertices.

If there were three nonzero neighborhood types, their type graph would be either a path or a triangle. A path gives two equal endpoint-neighborhoods, contradiction; a triangle gives three linearly independent neighborhood vectors, contradiction. Hence there are exactly two nonzero types, and they must be joined completely to each other. Thus $F$ is a complete bipartite graph plus isolated vertices:

with $a,b,c\ge1$. Hence $G$ is Seidel equivalent to $K_{a,b}\cup\overline K_c$.

Switching with respect to one of the three parts permutes the triple $(a,b,c)$, so choose the ordering

Then $i\le \lfloor n/3\rfloor$. Since $n\ge6$, the largest part $p\ge3$, except in the balanced case $i=j=p=n/3$. In that balanced case the quotient cubic has a double root, so the strict inequalities $\gamma<\rho$ fail. Thus the claimed parameter range holds.

For the second case,

the same interlacing argument applied to the third-smallest eigenvalue of every $4\times4$ principal submatrix gives $\alpha=1$. But

so $\overline G$ has eigenvalue $-1$ of multiplicity $n-3$ and satisfies the first case. Therefore $\overline G$ is Seidel equivalent to $K_{i,j}\cup\overline K_p$, equivalently

is Seidel equivalent to

This proves both parts.

Citation: No external resolution is used; the proof above is self-contained.