New regular two-graphs on 38 and 42 vertices

Abstract

All regular two-graphs having up to 36 vertices are known, and the first open case is the enumeration of two-graphs on 38 vertices. It is known that there are at least 191 regular two-graphs on 38 vertices and at least 18 regular two-graphs on 42 vertices. The number of descendants of these two-graphs is 6760 and 120, respectively.

In this paper, we classify strongly regular graphs with parameters (41,20,9,10) having nontrivial automorphisms and show that there are exactly 7152 such graphs. We enumerate all regular two-graphs on 38 and 42 vertices with at least one descendant whose full automorphism group is nontrivial and establish that there are at least 194 regular two- graphs on 38 vertices and at least 752 regular two-graphs on 42 vertices. Furthermore, we construct descendants with trivial automorphism group of newly constructed two-graphs and increase the number of known strongly regular graphs with parameters (37,18,8,9) and (41,20,9,10) to 6802 and 18439 respectively. This significantly increases the number of known strongly regular graphs with parameters (41,20,9,10).