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?

  • 3
    $\begingroup$ a keyword here is "rectagraph" (trinagle-free graph with every pair of vertices at distance 2 having exactly 2 common neighbours). $\endgroup$ – Dima Pasechnik Feb 20 '20 at 9:28
  • $\begingroup$ Thanks, I did not know this name. So basically srg(n,k,0,2) graphs are rectagraphs of diameter 2. $\endgroup$ – Florent Foucaud Feb 20 '20 at 10:03
  • 1
    $\begingroup$ Yes. A canonical reference is doi.org/10.1016/S0304-0208(08)73275-4 (can't get through the paywall though :- ( ) $\endgroup$ – Dima Pasechnik Feb 20 '20 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$.

  • $\begingroup$ Great, thanks! Actually the condition k=s^2+1 is referenced from this paper (but I don't see now where to derive this condition from): sciencedirect.com/science/article/pii/0012365X75900576 Perhaps you could edit your answer to refer to that. $\endgroup$ – Florent Foucaud Feb 20 '20 at 11:01
  • $\begingroup$ see my edit - as well, I replaced $s$ with $t$ to avoid notation clash. $\endgroup$ – Dima Pasechnik Feb 20 '20 at 20:50
  • $\begingroup$ Great, thank you! $\endgroup$ – Florent Foucaud Feb 21 '20 at 2:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.