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

$$S(G)_{uv}=\begin{cases} 0,&u=v,\\ -1,&uv\in E(G),\\ 1,&uv\notin E(G). \end{cases}$$

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

$$\beta,\alpha,\gamma,\rho$$

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

$$\beta<\alpha<0<\gamma<\rho .$$

Ordering the eigenvalues gives

$$\lambda_1=\beta,\qquad \lambda_2=\cdots=\lambda_{n-2}=\alpha,\qquad \lambda_{n-1}=\gamma,\qquad \lambda_n=\rho .$$

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

$$\lambda_2\le \mu_2(T)\le \lambda_{n-2},$$

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

$$\{-1,-1,-1,3\},\qquad \{-\sqrt5,-1,1,\sqrt5\},\qquad \{-3,1,1,1\}.$$

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

$$\alpha=-1.$$

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:

$$F\cong K_{a,b}\cup \overline K_c$$

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

$$1\le i\le j\le p,\qquad i+j+p=n.$$

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,

$$\rho<\gamma<0<\alpha<\beta,$$

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

$$S(\overline G)=-S(G),$$

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

$$G$$

is Seidel equivalent to

$$\overline{K_{i,j}\cup\overline K_p}.$$

This proves both parts.

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