A root graph that is locally the line graph of the Petersen graph

A.E. Brouwer, J.H. Koolen & M.H. Klin

August 24, 2000

Abstract

We construct a root graph on 192 vertices that is locally the line graph of the Petersen graph, a new distance-regular graph on 96 vertices (with intersection array {15, 10, 1; 1, 2, 15} and automorphism group 2^{4}.Sym(6)), and several new strongly regular graphs (with parameters (v, k, λ, μ) = (96, 20, 4, 4) and (96, 19, 2, 4)) and square 2-(96,20,4) designs.

1 Terminology and Notation

Our graphs are simple and undirected. A graph Γ has vertex set V Γ and edge set EΓ. The graph distance between two vertices u, v is denoted by d(u, v). We write u ∼ v when d(u, v) = 1, and say that u and v are adjacent, or are neighbours; we write u ≁ v when d(u, v) > 1 and say that u and v are nonadjacent. The set of neighbours of u in Γ is called Γ(u). The graph Γ is called locally P for some property or graph P when each local graph Γ(u) (graph induced on the set of neighbours of u) has property P or is isomorphic to the graph P.

2 Locally L(Petersen) graphs

Let Δ be the line graph of the Petersen graph Π. Then Δ is the unique distanceregular graph with intersection array {4, 2, 1; 1, 1, 4}, and has full group of automorphisms Sym(5). Its distance distribution diagram is

[figure: 1; 4; 1; 4; 1; 2; 1; 8; 2; 1; 4; 2; -; v = 15.]

Our aim in this note is to construct a root graph that is locally Δ and has the property that any two vertices at distance 2 have precisely 2 common neighbours, and to show that it is the unique graph with this property. But let us first look at arbitrary graphs that are locally Δ.

There exist infinite graphs that are locally Δ. Indeed, following a subset of {Ivanov, Pasechnik, Shpectorov}, we have the following construction.

Given a geometry (X, L) with lines of size 3, let G be the group

G = ⟨X| x^{2} = 1 = xyz for all x ∈ X and {x, y, z} ∈ L⟩.

Let Γ be the Cayley graph of G for the generating set X. Then Γ is a connected undirected graph that is locally the collinearity graph of (X, L), provided no collapse occurs. And collapse can be shown not to occur when enough geometric hyperplanes^{1} exist: If for any two points x, y ∈ X there is a hyperplane Z in (X, L) containing one but not the other, then the map u ↦ 1 if u ∈ Z and u ↦ a if u ∉ Z defines a homomorphism of G onto the group ⟨a | a^{2} = 1⟩, showing that x, y remain distinct in G. And if moreover for any three pairwise noncollinear points x, y, z ∈ X there is a hyperplane Z containing two of them but not the third, then xyz = 1 in G if and only if {x, y, z} ∈ L, and it follows that Γ is locally the line graph of (X, L).

In particular, this applies to Δ, where X is the set of edges of Π and L is the collection of concurrent triples of edges. Here the set of 10 vertices of Δ not in a pentagon of Π is a hyperplane, and one quickly sees that there are enough of these.

In this case, the group G (and hence the graph Γ) is infinite, since Π has two disjoint pentagons, and mapping u ∈ X to a, b or 1 when u is an edge of the first, of the second, or in neither of the pentagons, we find a homomorphism of G onto the infinite group ⟨a, b | a^{2} = b^{2} = 1⟩.

More generally, for a subgroup H of G and a subset X of G such that X = X^{−1}, consider the graph Γ(G, H, X) that has as vertices the cosets gH (g ∈ G) and edges g_{1}H ∼ g_{2}H when g_{2}^{−1}g_{1} ∈ HXH. (Any vertex transitive graph can be obtained in this way.) For H = 1 we have the Cayley graph construction as used above. If H is normal in G, then the neighbours of gH are the points gxH (x ∈ X). If moreover H is contained in G′, then the above arguments remain valid (they use certain quotients of G of order 2, and G′ is certainly contained in the kernel of the quotient map), and Γ(G, H, X) is locally Δ.

In particular, the graph Γ′ := Γ(G, G′, X) is locally Δ. It has 64 vertices. (Indeed, since G is generated by involutions, we may regard G/G′ as a binary vector space, in fact the universal projective embedding space of (X, L). Now the geometry (X, L) has universal embedding dimension 6 over F_{2} since the 10 × 15 incidence matrix has 2-rank 9, and we find |G/G′| = 2^{6} = 64.) The distance distribution diagram is

1A geometric hyperplane in a point-line geometry (X, L) is a set of points H such that every line not contained in H meets H in precisely one point.

[figure: 1; 15; 15; 30; 1; 2; 15; 1; 4; 2; 2; 8; 4; 4; 4; 8; 1; 15; 6; 1; 15; -; v = 64.]

3 Infinitely many locally L(Petersen) graphs

In this section we want to show that there are infinitely many finite and infinitely many infinite locally Δ graphs. To this end, let us first determine when two graphs Γ(G, H, X) (with H normal in G) are isomorphic.

Clearly, if ψ is an automorphism of Δ, then ψ induces a permutation of X that extends to an automorphism of G and of Γ, and we find that Γ(G, H, X) ≃ Γ(G, ψ(H), X).

Conversely, if Γ(G, H, X) ≃ Γ(G, K, X), then K = ψ(H) for some automorphism ψ of Δ. Indeed, this follows from

Lemma 3.1 There is a unique local isomorphism ϕ : Γ → Γ(G, H, X) that maps a to aH for all a ∈ {1} ∪ X.

Proof: Let ϕ be such a morphism. We show that ϕ(g) = gH for all g ∈ G by induction on d(g, 1), where d is the graph distance in Γ. For d(g, 1) ≤ 1 this is true by hypothesis. Let d(g, 1) = i + 1 > 1 and write g = az with d(a, 1) = i and z ∈ X. Define an automorphism ψ of Δ by ϕ(ax) = aψ(x)H. By induction hypothesis, ψ(x) = x for the x with d(ax, 1) ≤ i so that ψ fixes a vertex and its four neighbours, and hence is the identity. Hence ϕ(g) = ϕ(az) = azH = gH. □

So, in order to show that there are infinitely many finite and infinitely many infinite locally Δ graphs (pairwise nonisomorphic), it suffices to show that G′ contains infinitely many normal subgroups H of G, both of finite and of infinite index. But this is very easy. For example, if a, b are two nonadjacent vertices of Δ, then if we add the relation [a, b]^{m} = 1 to the defining relations of G, we obtain a quotient in which [a, b] has order precisely m; if K is the kernel of the quotient map, then H := K ∩ G′ is of infinite index in G′. On the other hand, if, for two disjoint pentagons in Π, we add the relations that all edges of one are equal (say to a), and all edges of the other are equal (say to b), and all remaining edges are 1, and [a, b]^{m} = 1, and define K and H as before, then K is of index 4m in G, and H is of index m in G′.

(So, as a byproduct, we find that there exist locally Δ graphs on 64m vertices for every natural number m.)

4 A distance-regular graph that is locally L(Petersen) and a double cover

Let V be a 4-dimensional vector space over F_{2}, provided with a nondegenerate symplectic form f. The generalized quadrangle with parameters GQ(2, 2) we find by taking the points and totally isotropic (t.i.) lines in the projective space P V has six ovoids and six spreads. Each point is on two ovoids and can be viewed as a transposition on Ω, the set of ovoids. Each line has three points and can be viewed as a syntheme (product of three commuting transpositions) on Ω. Dually, the lines and points can be regarded as transpositions and synthemes on Σ, the set of spreads. For each nonzero v ∈ V, let σ_{v} be the syntheme that the point ⟨v⟩ induces on Σ.

Define a graph Z with vertex set V × Σ by letting (u, S) ∼ (v, T) if u ≠ v and σ_{v−u}(S) = T. It is straightforward to check that this defines a distanceregular graph with intersection array {15, 10, 1; 1, 2, 15} and automorphism group 2^{4}.Sym(6), with point stabilizer Sym(5) acting rank 5 with suborbits 1 + 5 + 15 + 15 + 60. This graph is locally Δ: the local graph at (0, S) is the collinearity graph of GQ(2, 2) from which the spread S has been removed. It has distance distribution diagram

[figure: 1; 15; 1; 15; 4; 10; 2; 75; 12; 1; 15; 5; -; v = 96.]

It is an antipodal 6-cover of K_{16}. The graph Z_{1} ∪ Z_{3}, obtained by calling vertices of Z adjacent when they have distance 1 or 3 in Z, is strongly regular with parameters (v, k, λ, μ) = (96, 20, 4, 4).

(These graphs are new: the known graphs with the same parameters are obtained by taking GQ(5, 3) or GQ(5, 3) minus a spread, and these have local graphs that are unions of 5-cliques.)

The adjacency matrix of this latter strongly regular graph is also the incidence matrix of a square 2-(96,20,4) design.

In the next section, we shall meet a graph that will turn out to be a double cover of the graph Z just constructed. Let us construct this double cover in the present setting.

Consider the Sp(6, 2) geometry (P, L). The point set P is the set of projective points of a vector space V of dimension 6 over F_{2} provided with a nondegenerate symplectic form f, and L is the set of totally isotropic (t.i.) lines. Fix a point ∞ ∈ P, and let X = P \ ∞^{⊥}, so that |X| = 32. For p ∈ P, the local space p^{⊥}/p (of t.i. lines and planes on p) has the structure of a Sp(4, 2) geometry (a generalized quadrangle with parameters GQ(2, 2)).

Let the vertices of Ẑ be the ordered pairs (x, S) where x ∈ X and S is a spread in ∞^{⊥}/∞. Let (x, S) ∼ (y, T) if f(x, y) = 0 and x ≠ y and S ≠ T and x + y ∈ π ∈ S ∩ T for some t.i. plane π on ∞. (Note that given x, y, S with collinear x, y, there is a unique T satisfying this requirement, since in Sp(4, 2) each line is in 2 spreads.)

Now Ẑ is a graph on 32 × 6 = 192 vertices, a six-fold cover of the collinearity graph of X. This collinearity graph has distance distribution diagram

[figure: 1; 15; 1; 15; 6; 8; 8; 15; 6; 1; 15; 1; -; v = 32]

and is locally GQ(2, 2). In the six-fold cover, the valency remains 15, but the local graph at (x, S) can be identified with GQ(2, 2) from which the spread S has been removed. (If (y, T) ∼ (x, S), then map (y, T) to the point ⟨∞, x + y⟩ of ∞^{⊥}/∞.)

Thus, Ẑ is locally Δ.

It is a double cover of Z.

(Indeed, Choose x_{0} ∈ X. Then ∞^{⊥}/∞ and {∞, x_{0}}^{⊥} can be canonically identified. Map x_{0} to 0 and x ∈ X \ {x_{0}} to the vector spanning the projective point ⟨x, ∞, x_{0}⟩ ∩ {∞, x_{0}}^{⊥}.)

One may verify that any two vertices in Ẑ at mutual distance 2 have precisely 2 common neighbours.

(Indeed, if (x, S) ∼ (y, T) ∼ (z, U) and locally at (y, T) the vertices (x, S) and (z, U) have distance 3, then f(x, z) = 0 and S = U. Now the plane π = ⟨x, y, z⟩ is t.i., and meets ∞^{⊥} in a line L. If u is the fourth point of π \ L, then (u, T) is the unique common neighbour of (x, S) and (z, U) distinct from (y, T). On the other hand, if (x, S) and (z, U) have distance 2 locally at (y, T), then we already see a second common neighbour in the neighbourhood of (y, T). If there were any further common neighbour, we would find a 2-clique extension of a quadrangle in Ẑ, where all spreads involved in its 8 vertices are distinct. But there are only 6 spreads. Contradiction.)

5 A root graph that is locally L(Petersen)

A root graph is a connected graph P that admits a map r ↦ \overline{r} mapping its vertices into some Euclidean space R^{n} in such a way that for all vertices r, s of P the squared distance ||\overline{r} − \overline{s}||^{2} is an even integer, and such that if r ∼ s then ||\overline{r} − \overline{s}||^{2} = 2, and if d(r, s) = 2 then ||\overline{r} − \overline{s}||^{2} = 4.

An obvious example of a root graph is the halved n-cube that has as vertices all even weight vectors of length n, adjacent iff the difference has weight 2.

Any connected induced subgraph of a root graph is again a root graph, so root graphs abound. However, classification becomes possible if one imposes some regularity, see [BCN] §3.14-15, and [7] §6.3.

Construct a root graph P as follows: take as vertex set the collection of all subsets A of V Π such that |A| is even and the subgraph Π_{A} of Π induced on A has an even number of non-edges. Let two vertices A and B of P be adjacent when their symmetric difference A + B has size 2. Clearly, this is a subgraph of the halved 10-cube, and it is easy to check that it is connected, so P is really a root graph. P has distance distribution diagram around ∅:

[figure: 1; 15; 15; 60; 5; 60; 5; 15; 15; 1; 15; 1; 4; 2; 2; 8; 2; -; 2; 8; 1; 3; 4; 1; 5; 4; 4; 1; 12; 1; 4; -; 12; 1; 5; 8; 2; 2; 8; -; 3; 1; -; 2; 2; 4; 1; 15; .]

Clearly, this graph is locally Δ at ∅ and any two nonadjacent neighbours of ∅ have precisely 2 common neighbours. We shall show that its group of automorphisms is transitive, from which it will follow that P is locally Δ and has ‘μ = 2’ everywhere. We start by rephrasing the definition of P.

Consider the 10-dimensional vector space V over F_{2} with basis V Π. Let W be the hyperplane {x ∈ V | ∑ x_{a} = 0}. Let Q be the quadratic form on V defined by Q(x) = ∑ x_{a}x_{b} where the sum is over the pairs {a, b} of nonadjacent vertices in Π. Our graph P has as vertex set {x ∈ W |Q(x) = 0}. Since Q has a radical R of dimension 5 which is contained in W, and induces an elliptic quadric (O_{4}^{−}(2) geometry) on W/R, we find that |V P| = 32 · 6 = 192. Two vertices are adjacent when they differ by a vector of weight 2. This description shows that P has a translation group of size 32 and a point stabilizer Sym(5) acting transitively on the 15 neighbours of 0, and permuting the 5 nonzero cosets of R. Remains to show that the vertex 0 can be moved to a nonzero coset of R. If we identify V Π with the set of pairs from the 5-set {0, 1, 2, 3, 4}, an automorphism of P is given by the composition of the coordinate permutation (a ↦ {1, 2, 3, 4} \ a if 0 ∉ a, and a ↦ a if 0 ∈ a) with the translation x ↦ x + e_{12} + e_{34}. (Indeed, this trivially preserves adjacency and membership of W, so we only have to check that this preserves the value of Q. But if ∑_{0∈a} x_{a} = i, then this map changes Q by i(i+1), and consequently preserves Q.) Since this automorphism preserves the partition into cosets of R (since it preserves Q), and moves 0 to a neighbour, we have shown that G := Aut(P) has order 192 × 5! = 32 × 6! and structure 2^{5}.Sym(6). It acts transitively on incident (vertex,edge) pairs. Its central involution is x ↦ x + 1.

6 Uniqueness

Let T be an arbitrary root graph that is locally Δ, with root representation t ↦ \overline{t} for t ∈ V T. The lattice Λ generated by the vectors \overline{s} − \overline{t} for adjacent vertices s, t ∈ V T is a root lattice. Since T is locally connected, this lattice is irreducible (by BCN 3.14.1) and hence one of A_{n}, D_{n}, E_{6}, E_{7} or E_{8}.

Fix a vertex ∞ of T. We may assume (by shifting the representation if necessary) that \overline{∞} = 0. Look at the images of the neighbours of ∞. If A is the adjacency matrix of Δ, then A has spectrum 4^{1} 2^{5} (−1)^{4} (−2)^{5} and hence the Gram matrix of \overline{T(∞)} (which equals 2(A + 2I)) has rank 10, which means that \overline{T(∞)} spans a 10-space. In particular, Λ cannot be E_{6}, E_{7} or E_{8}, and we may assume that Λ ⊆ Z^{n}.

From BCN, 3.14.6 it follows that if d(s, t) = 2, then \overline{s} − \overline{t} ≠ 2e_{i} (where e_{i} is a base vector in Z^{n}), and it follows easily that we may choose \overline{T(∞)} to be of the form {e_{a} + e_{b}|{a, b} ∈ V Δ}.

Next, we would like to conclude n = 10; in other words: the ten coordinate positions in which the 15 vectors \overline{t} for t ∼ s differ from \overline{s} should be the same for every s ∈ V T.

Let us add the assumption μ = 2 (that is: every two vertices at distance two have precisely 2 common neighbours) to our hypothesis. Now n = 10 follows immediately: Look at the neighbourhood of a vertex s with s ∼ ∞, say \overline{s} = e_{a} + e_{b}, where ab is an edge of Π. Let c be a vertex of Π. We want to show that for some neighbour t of s the vector \overline{t} differs from \overline{s} in the c-coordinate. If c equals a or b then take t = ∞. If c is a neighbour of a, say, then the edges ab and ac are adjacent in Δ, and we can take t with \overline{t} = e_{a} + e_{c}. Finally, if c is a nonneighbour of a, then let cd be an edge antipodal (in Δ) to ab. Let r be the vertex adjacent to ∞ represented by e_{c} + e_{d}. Now d(r, s) = 2 so r and s have a common neighbour t other than ∞. We find that \overline{t} = e_{a} +e_{b} +e_{c} +e_{d}, completing the proof of n = 10.

Is the representation of T uniquely determined, given the representation of ∞ and its neighbours? Yes: we just saw that the neighbours of the point s represented by e_{a} + e_{b} have known representation, except perhaps for the two common neighbours of s and t, where \overline{t} = e_{a} + e_{c}, at distance 2 from ∞. These are represented by e_{a} + e_{b} + e_{c} ± e_{x} for two different x. Such a vertex x of Π must have distance two to each of a, b, c, for if there were an edge, say, cx, and p is the neighbour of s and t represented by e_{a} + e_{b} + e_{c} ± e_{x}, then the neighbour r of ∞ represented by e_{c}+e_{x} had distance at most 2 to p (since t is a common neighbour) and looking at ||\overline{p}−\overline{r}||^{2} we see that the sign must be + and the distance 1, so that ∞ and p have at least three common neighbours, contradicting our assumption μ = 2. But there are only two vertices with distance two to each of a, b, c, so we have to take these two, and the representation of all of T is uniquely determined.

Consequently, T is a cover of P (with representation constant on the fibers). In particular it now follows that Ẑ ≃ P since they have the same number of vertices.

Can nontrivial covers occur? No: By the definition of root graph, triangles lift to triangles. Since μ = 2 for both the graph and its cover, quadrangles lift to quadrangles. So, it suffices to show that an arbitrary circuit in P of length at least 5 is the sum of shorter circuits. Consider an i-circuit, i ≥ 5, starting and ending in 0. We may assume that distances measured in the circuit equal graph distances. If i ≥ 7, then let c, c′ be vertices of the circuit with d(0, c) = d(0, c′) = 3, d(c, c′) = i − 6. If a is on a geodesic from 0 to c, and a′ on a geodesic from 0 to c′, and d(a, a′) ≤ 1, then we can write the circuit as a sum of shorter circuits. But for each c the possible pairs a cover at least 6 elements of Π, and there are only 10, so i-circuits with i ≥ 7 can always be shortened. Assume 5 ≤ i ≤ 6. Let b, b′ be vertices with d(0, b) = d(0, b′) = 2, d(b, b′) = i − 4. If a is a common neighbour of 0 and b, and a′ is a common neighbour of 0 and b′, and d(a, a′) ≤ 1, then we can write the circuit as a sum of shorter circuits. So we may assume that the at least 3 elements of Π occurring in the common neighbours of 0 and b differ from those occurring in the common neighbours of 0 and b′. But then d(b, b′) ≥ 2, so that i = 6. And the only way this can happen has b and b′ joined by a path of length 3 consisting of weight 4 vectors, so that this hexagon is the sum of four pentagons. Thus, no covers occur.

Theorem 6.1 There is a unique root graph with μ = 2 that is locally the line graph of the Petersen graph. It has 192 vertices and group 2^{5}.Sym(6) acting flag-transitively.

7 Designs and strongly regular graphs on 96 points

The first two authors wrote the above in 1994, but never published it. The third author described a strongly regular graph K with parameters (96, 20, 4, 4) during the Conference on Association Schemes, Codes and Designs in Pohang, Korea, July 2000 (and had already announced two more, say K′, K′′, in [6]). These three graphs were found using the computer algebra package COCO [3]. Now that K looked very much like the graph Z_{1} ∪ Z_{3} constructed above, let us study the connections.

7.1 Strongly regular graphs with parameters (96,20,4,4)

The textual description of K in terms of Petersen graphs turned out to be flawed; however, the computer files of the third author indicated a construction using spreads, essentially identical to the construction of Z_{1} ∪ Z_{3} above.

The graphs K′, K′′ were found by asking COCO for all strongly regular graphs obtained by merging classes in the 15-class scheme of (Sym(4)×Sym(4)).2 acting on the coloured 1-factors of K_{4,4}, where each 1-factor has one red and three blue edges. This yields two strongly regular graphs, both with parameters (96, 20, 4, 4) and (transitive) automorphism group of order 11520, where K′ has suborbits of sizes 1,5,15,15,60 and K′′ has suborbits of sizes 1,15,20,30,30. In particular, K′′ is edge transtive.

Now (Sym(4) × Sym(4)).2 is a subgroup of 2^{4}.Sym(6) (namely the subgroup fixing a 3 + 3 split of the 6-set), and the permutation representation of the latter, acting on V Z, restricts to that of the former, acting on V K′, and COCO finds precisely one strongly regular graph by merging classes in this 4-class scheme, with suborbits 1,5,15,15,60, so K′ is isomorphic to Z_{1} ∪ Z_{3} found above (and to K). The group of K′′ is 2^{5} · Alt(6).

If we only require a group Sym(4)×Sym(4) we find one further graph, labeled A_{0} below, with Sym(4) × Sym(4) of order 576 as full group of automorphisms.

In the literature one finds one other strongly regular graph with parameters (96, 20, 4, 4), namely the collinearity graph of the (unique) generalized quadrangle of order (5, 3) (cf. [2, 10]). It has automorphism group 2^{6}.3.Sym(6) of order 138240 acting rank 4 with subdegrees 1, 20, 60, 15.

(Wallis [12] gave a general construction, that in the present case boils down to: Take the affine plane AG(2, 4) and number its parallel classes arbitrarily 1, ..., 5. Let (Q, ∗) be a commutative quasigroup of order 6 such that q ∗ q = 0 for all q ∈ Q, and let X be the point set of the affine plane. Make a strongly regular graph with point set Q × X, letting (i, x) ∼ (j, y) whenever i ∗ j ≠ 0 and x, y lie together in a line in parallel class i ∗ j. However, up to isomorphism there is only one possible choice for the ingredients here, and the result is the collinearity graph of GQ(5, 3).)

Below we shall find several more strongly regular graphs with parameters (96, 20, 4, 4). Here a table with a few properties. The graphs labeled X_{i} for some letter X, give the same square design iff they have the same letter X.

Name  # K_{4} # K_{5} # K_{6} # K_{2,4} |Autgp| # orbits
GQ(5, 3)  960  384  64  3600  138240  1
K′  480  96  16  720  11520  1
K′′  480  96  0  2160  11520  1
A_{0}  288  0  0  1440  576  1
A_{1}  192  0  0  1104  768  1
A_{2}  192  0  0  656  128  4
A_{3}  192  0  0  1104  768  1
A_{4}  192  0  0  912  256  2
B_{0}  192  0  0  144  1536  1
C_{0}  192  0  0  720  768  1
D_{0}  160  0  0  560  16  6
D_{1}  160  0  0  560  16  6
D_{2}  96  0  0  480  16  6
D_{3}  192  0  0  480  16  6
E_{0}  384  24  4  864  144  2
E_{1}  224  0  0  592  64  2
E_{2}  96  0  0  560  32  3
E_{3}  192  0  0  640  32  3
F_{0}  384  24  0  1500  48  4
F_{1}  192  0  0  896  64  2
F_{2}  192  0  0  1164  48  4
F_{3}  192  0  0  768  32  3
F_{4}  192  0  0  784  32  3
F_{5}  96  0  0  704  64  2
F_{6}  96  0  0  640  32  3
F_{7}  224  0  0  608  32  3
F_{8}  192  0  0  640  64  2
F_{9}  96  0  0  576  64  2
F_{10}  96  0  0  528  32  3
F_{11}  192  0  0  896  64  2
F_{12}  96  0  0  896  64  2

7.2 Spreads

In [1] it is shown that there is a 1-1 correspondence between antipodal distanceregular graphs with intersection array {st, s(t − 1), 1; 1, t − 1, st} and strongly regular graphs with parameters (v, k, λ, μ) = ((s + 1)(st + 1), s(t + 1), s − 1, t + 1) with a specified partition of the point set into (s + 1)-cliques. The obvious example of this situation is a generalized quadrangle of order (s, t) with a spread, and Godsil & Hensel [4] asked whether there are any other examples.

Above we found three strongly regular graphs with parameters (96, 20, 4, 4). The graph K′ contains precisely 16 6-cliques, and hence has a unique spread, thus providing a non-GQ example.

The graph K′′ does not have spreads, indeed, it has no 6-cliques. However, it has 96 5-cliques, precisely one on each edge, and we see that K′′ is the collinearity graph of a flag-transitive self-dual partial linear space with 5 points per line and 5 lines on each point.

The collinearity graph of GQ(5, 3) has 24 spreads, all equivalent under the automorphism group (cf. Payne [9]), and we find a distance-regular graph with parameters {15, 10, 1; 1, 2, 15} and group of order 5760 acting rank 5.

7.3 Square 2-(96,20,4) designs

The adjacency matrix of K′ is the incidence matrix of a square 2-(96,20,4) design with automorphism group of order 552960. The design has two conjugacy classes class of fixpoint-free polarities, and we find two strongly regular graphs with parameters (96,20,4,4). One is K′ again. The other is new; it is labeled B_{0} in the table above. There is also a conjugacy class of polarities with all points absolute, and we find a strongly regular graph with parameters (96,19,2,4) and vertex-transitive groups of order 9216.

The adjacency matrix of K′′ is the incidence matrix of a square 2-(96,20,4) design with automorphism group of order 184320. This design has two conjugacy classes of fixpoint-free polarities, and we find strongly regular graphs with parameters (96,20,4,4) and vertex-transitive groups of orders 11520 and 768, respectively. The former is K′′, the latter is new; it is labeled C_{0} in the table above.

The adjacency matrix of A_{0} is the incidence matrix of a square 2-(96,20,4) design with automorphism group of order 9216. This design has five conjugacy classes of fixpoint-free polarities, and we find four more strongly regular graphs with parameters (96,20,4,4), labeled A_{1}, ..., A_{4} in the table above.

In the literature one finds two 2-(96,20,4) designs with abelian difference set (in the groups (2)(4)^{2}(3), (2)^{3}(4)(3) and (2)^{5}(3)). Let us look at the three difference set given explicitly in [5], p.302.

The first one was given incorrectly.

The second has a group of order 96 and four conjugacy classes of fixpoint-free polarities, and we find four strongly regular graphs with parameters (96,20,4,4), labeled D_{0}, ..., D_{3} in the table above.

The third has a group of order 576 and four conjugacy classes of fixpoint-free polarities, and we find four strongly regular graphs with parameters (96,20,4,4), labeled E_{0}, ..., E_{3} in the table above. There are two conjugacy classes of polarities with all points absolute, and we find two strongly regular graphs with parameters (96,19,2,4) and groups of order 144, 192, respectively.

These latter two difference sets are McFarland difference sets, and there is freedom in the choice. We have not exhaustively investigated other choices. A random attempt in the group (2)^{5}(3) (difference set {000001, 000101, 001001, 001101, 000002, 010002, 100002, 110002, 000010, 010110, 101010, 111110, 000011, 011111, 100111, 111011, 000112, 011112, 101012, 110012}) yielded a design with group of order 192 from which the graphs F_{0}, ..., F_{12} are derived. No doubt there are lots of graphs and designs with these parameters.

7.4 Strongly regular graphs with parameters (96,19,2,4)

In the above, we found three strongly regular graphs with parameters (96, 19, 2, 4) (with groups of order 9216, 192, 144). The literature (cf. [2], p. 101) contains one other construction, by Haemers, as follows. Construct GQ(5, 3) by taking as points the lines in AG(3, 4) in one of six directions, where these directions form a hyperoval in the plane at infinity, taking two lines to be adjacent when they intersect. Partition the hyperoval into three pairs {d, d′}. Redefine adjacency by replacing each of the twelve subgraphs K_{4,4} found on a plane with directions {d, d′} by their complement 2K_{4}. This graph has a transitive group of order 9216, and has 24 4-cliques partitioning the point set. Checking shows that this is the same graph as the one with group of order 9216 we found earlier. (From Haemers graph we can reconstruct GQ(5, 3) by deleting the edges of the 24 4-cliques, and adding edges between pairs of points that have a 4-cycle (and not a 4-coclique) as mu-graph.)

7.5 Distance-regular graphs with array {15, 10, 1; 1, 2, 15}

In the above, we found two distance-regular graphs with the intersection array {15, 10, 1; 1, 2, 15}, with groups of order 5760 and 11520, respectively.

8 Acknowledgments

We used COCO [3], GAP [11], and Nauty [8].

References

[BCN] A. E. Brouwer, A. M. Cohen & A. Neumaier, Distance-regular graphs, Springer, Heidelberg, 1989.

[1] A. E. Brouwer, Distance regular graphs of diameter 3 and strongly regular graphs, Discrete Math. 49 (1984) 101–103.

[2] A. E. Brouwer & J. H. van Lint, Strongly regular graphs and partial geometries, pp. 85–122 in: Enumeration and Design - Proc. Silver Jubilee Conference on Combinatorics, Waterloo, 1982, D.M. Jackson & S.A. Vanstone (eds.), Academic Press, Toronto, 1984.

[3] I. A. Faradzev & M. H. Klin, Computer package for computations with coherent configurations, Proc. of the 1991 Intern. Symp. on Symb. and Algebr. Computations, ISSAC ’91 (Bonn, July 15-17, 1991), ACM Press, 219-223.

[4] C. D. Godsil & A. D. Hensel, Distance regular covers of the complete graph, J. Combin. Theory Ser. B 56 (1992) 205–238.

[5] D. Jungnickel & A. Pott, Difference sets: Abelian, pp. 297–307 in: The CRC Handbook of Combinatorial Designs, C. J. Colbourn & J. H. Dinitz, eds., CRC Press, Boca Raton, 1996.

[6] M. H. Klin, Strongly regular Cayley graphs on 96 vertices, J. Geometry 65 (1999) 15–16.

[7] J. H. Koolen, Euclidean representations and substructures of distance-regular graphs, Thesis, Techn. Univ. Eindhoven, 1994.

[8] B.D. McKay, Nauty users guide (version 1.5), Technical Report TR-CS-90-02, Computer Science Department, Australian National University, 1990.

[9] S. E. Payne, The generalized quadrangle with (s, t) = (3, 5), Proceedings of the Twenty-first Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1990), Congr. Numer. 77 (1990), 5–29.

[10] S. E. Payne & J. A. Thas, Finite generalized quadrangles, Pitman, Boston, 1984.

[11] M. Schönert et al., GAP: Groups, Algorithms and Programming, Aachen, April 1992.

[12] W. D. Wallis, Construction of strongly regular graphs using affine designs, Bull. Austr. Math. Soc. 4 (1971) 41–49.