New prolific constructions of strongly regular graphs

Abstract

We present a purely combinatorial construction of strongly regular graphs with geometric parameters. The construction produces hyperexponentially many graphs, and uses neither linear algebra nor groups. Among the graphs constructed, there are graphs with pa- rameters of a generalized quadrangle GQðn � 1; n þ 1Þ which further produce distance regular covers of complete graphs. In this paper we present an exceptionally prolific construction of strongly regular graphs. We use the word ''prolific'' informally, but in a rather strict sense. Thus, there are prolific constructions of strongly regular graphs from Latin squares, from Steiner triple systems, from collections of mutually orthogonal Latin squares (of prime power order), etc. What is especially interesting about our construction is that it produces graphs with geometricparameters (in the sense of (1)); in partic ular, with those of generalized quadrangles GQðni; n þ iÞ for i ¼ 0; G1. Moreover, the graphs with parameters of GQðn � 1; n þ 1Þ, by virtue of the construction, will have spreads of n- cliques; removing the edges of these cliques one obtains distance regular n-covers of the complete graph Kn2 . In this way one can find, for instance, distance regular graphs of diameter 3 with the trivial group of automorphisms. As building blocks of the construction we shall use certain 2-designs: resolvable de- signs with constant intersection of non-parallel lines. In this paper we shall call them a‰ne designs. Definition 1. An a‰ne design is a 2-design with the following two properties: