Strongly regular graphs with no triangles: challenges and computer algebra
results
Matan Ziv-Av
A strongly regular graph (briefly SRG) with parameters (v,k,\lambda,\mu)
is a regular graph of valency k such that every two neighours have
exactly \lambda common neighbours, and every two non-neighbours have
exactly \mu common neighbours. An SRG is called primitive if both the
graph and its complement are connected.
We consider primitive SRGs with no triangles (that is \lambda=0, briefly
called tfSRGs). The most famous SRG with no triangles, denoted by
NL_2(10), has parameters (100, 22, 0, 6), it was described in the paper
by Higman and Sims in 1968 in the course of the discovery of a new
sporadic simple group HS. Twelve years earlier, Dale Mesner Constructed
this graph, Denoting it by NL_2(10). Mesner constructed NL_2(10) by way
of an equitable partition of this graph.
This construction raises two enumeration problems relating to tfSRGs.
One is embedding smaller tfSRGs in larger ones, and the other is
equitable paritions of tfSRGS. We present complete computer aided
enumeration of embeddings of tfSRGs inside known tfSRGs, and computer
aided emumeration of equitable partitions of tfSRG of size up to 50.