7
$\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$ Commented 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$ Commented 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$ Commented Feb 20, 2020 at 10:04

1 Answer 1

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .