6
$\begingroup$

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?

$\endgroup$
3
  • 3
    $\begingroup$ a keyword here is "rectagraph" (trinagle-free graph with every pair of vertices at distance 2 having exactly 2 common neighbours). $\endgroup$ Feb 20, 2020 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$ Feb 20, 2020 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$ Feb 20, 2020 at 10:04

1 Answer 1

5
$\begingroup$

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$.

$\endgroup$
3
  • $\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$ Feb 20, 2020 at 11:01
  • $\begingroup$ see my edit - as well, I replaced $s$ with $t$ to avoid notation clash. $\endgroup$ Feb 20, 2020 at 20:50
  • $\begingroup$ Great, thank you! $\endgroup$ Feb 21, 2020 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.