# What is known about the non-existence of strongly regular graphs srg(n,k,0,2)?

Only few strongly regular graphs with parameters $$\lambda=0$$ (triangle-free) and $$\mu=2$$ (any two non-adjacent vertices have exactly two common neighbors) are known, see the wikipedia page: the 4-cycle, the Clebsch graph and the Sims-Gewirtz graph.

I am looking for any information about the potential existence of more such graphs. For which values of $$n$$ and $$k$$ are they known not to exist?

• a keyword here is "rectagraph" (trinagle-free graph with every pair of vertices at distance 2 having exactly 2 common neighbours). Feb 20, 2020 at 9:28
• Thanks, I did not know this name. So basically srg(n,k,0,2) graphs are rectagraphs of diameter 2. Feb 20, 2020 at 10:03
• Yes. A canonical reference is doi.org/10.1016/S0304-0208(08)73275-4 (can't get through the paywall though :- ( ) Feb 20, 2020 at 10:04

Example 1 in A.Neumaier paper says in partcular that the vertex degree in this case must be $$k=t^2+1$$, for $$t$$ not divisible by 4. As well, the number of vertices is $$v=1+k+\binom{k}{2}$$. The examples you list correspond to $$t=2,3$$. The next possible parameter set corresponds to $$t=5$$, so you have $$v=352$$, $$k=26$$. A.Brouwer's database lists this tuple of parameters as feasible, but no examples known. Similarly for $$t=6,7$$ you have feasible sets of parameters $$v=704,1276$$, resp. $$k=37,50$$, but no examples known.
To see that $$k=t^2+1$$, note that the 2nd eigenvalue of the adjacency matrix is $$r:=\frac{1}{2}\left[(\lambda-\mu)+\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}\right]=-1+\sqrt{k-1},\quad \text{i.e. t^2:=(r+1)^2=k-1.}$$ Similarly, the 3rd eigenvalue is $$s:=-1-\sqrt{k-1}$$, and one can compute their multiplicites, see e.g. Brouwer-van Lint, p.87 to rule out the case $$t$$ divisible by 4. Namely, the multiplicity of $$r$$ is given by $$-\frac{k(s+1)(k-s)}{(k+rs)(r-s)}=\frac{k\sqrt{k-1}(k+1+\sqrt{k-1})}{4\sqrt{k-1}}=\frac{(t^2+1)(t^2+2+t)}{4},$$ which cannot be an integer if $$4|t$$.
• see my edit - as well, I replaced $s$ with $t$ to avoid notation clash. Feb 20, 2020 at 20:50