On small strongly regular graphs with an automorphism of order $3$

Martin Mačaj
Comenius University

Anton Koval
Comenius University

PDF

Minisymposium: ASSOCIATION SCHEMES

Content: A graph is a strongly regular graph with parameters $(n,k,\lambda,\mu)$ if it is a $k$-regular graph of order $n$ such that each pair of adjacent vertices has in $G$ exactly $\lambda$ common neighbors and each pair of non-adjacent vertices has in $G$ exactly $\mu$ common neighbors. There exist several necessary conditions for parameter sets $(n,k,\lambda,\mu)$ to admit an existence of a strongly regular graph. Parameter sets which satisfy all such conditions are called feasible. Although the existence of a strongly regular graph is solved for all feasible parameter sets with $n\leq 50$, the complete classification is still open for parameter sets $(37,18,8,9)$, $(41,20,9,10)$, $(45,22,10,11)$, $(49,24,11,12)$, $(49, 18, 7,6)$ and $(50,21,8,9)$. By exhaustive computer search we obtain the full list of strongly regular graphs on up to $50$ vertices with an automorphism of order $3$. Further, for parameter sets $(37,18,8,9)$, $(41,20,9,10)$, $(45,22,10,11)$, $(49,24,11,12)$, $(49, 18, 7,6)$ and $(50,21,8,9)$ we determine a class of strongly regular graphs which contains all the $Z_3$ graphs and is closed under particular instances of partial switching defined by Godsil-McKay and Behbahani-Lam-Ostergaard, respectively. As a corollary, we significantly extend list of known regular two-graphs on at most $50$ vertices. (Recall that a two-graph is a set of (unordered) triples chosen from a finite vertex set X, such that every (unordered) quadruple from X contains an even number of triples of the two-graph. A regular two-graph has the property that every pair of vertices lies in the same number of triples of the two-graph.)

Back to all abstracts