Classification of small (0,2)-graphs

Andries E. Brouwer

Department of Mathematics, Technological University Eindhoven, P.O. Box 513, 5600 MB Eindhoven, The Netherlands

October 1, 2005

Abstract We find the graphs of valency at most 7 with the property that any two nonadjacent vertices have either 0 or 2 common neighbours. In particular, we find all semibiplanes of block size at most 7.

1 Introduction

A (0, 2)-graph is a connected graph such that any two vertices have either 0 or 2 common neighbours. A rectagraph is a (0, 2)-graph without triangles. A semibiplane is a connected point-block incidence structure such that any two points are in either 0 or 2 common blocks, and any two blocks have either 0 or 2 common points. Clearly, the incidence graph of a semibiplane is a bipartite (0, 2)-graph (and conversely).

These topics have been studied by various authors. Semibiplanes were introduced by Dan Hughes [2] in the study of projective planes with involution, and are the topic of the thesis [8] of Peter Wild. Rectagraphs were introduced by Arnold Neumaier [7] in the study of diagram geometries. Semibiplanes provide examples of geometries with c.c* diagram (where the objects are the points, the pairs, and the blocks), and these have been studied under various assumptions on the group of automorphisms. Martyn Mulder [6] showed that (0, 2)-graphs are regular, say of valency k, and that the number v of vertices and the diameter d satisfy v ≤ 2^{k} and d ≤ k with in both cases equality only for the hypercube.

During GAC 3 (Oisterwijk, 2005) Kris Coolsaet asked whether it is possible to completely classify all rectagraphs with valency 6. That is indeed possible, and one can go a bit further.

There is earlier classification work. Peter Wild [9] determined all semibiplanes of block size at most 6. Michel Mollard [4] determined all (0, 2)-graphs on at most 31 vertices (and finds that these have valency at most 7).

Here we first show (§3) how to reduce the classification problem to the bipartite case. This case was done by computer, and the results are given in §13. Given these results we can go back and find the nonbipartite (0, 2)-graphs with k ≤ 7. The results are given in §14.

For each graph some statistics are given (such as number of vertices, valency, diameter, distance distributions, group size, group orbits), enough to recognize the graph. From the computer search one gets ugly 0-1 matrices, but in fact many of the graphs have a largish group of automorphisms, and a nice description. In §§3-12 we give some constructions of (0,2)-graphs that are referred to in the tables.

2 Parameter restriction

The number of closed walks of length 4 without repeated vertices is vk(k − 1)/8 and this must be integral, so for k = 2, 3 (mod 4) we have 4|v, and for k = 4, 5 (mod 8) we have 2|v.

3 Doubling

The bipartite double Δ of a graph Γ is the (bipartite) graph with vertices x^{+} and x^{−} for each vertex x of Γ, and edges x^{−}y^{+} and x^{+}y^{−} for each edge xy of Γ. It is connected if and only if Γ is connected and nonbipartite. It is a (0, 2)-graph if and only if Γ is a nonbipartite (0, 2)-graph, and then has the same valency as Γ.

This shows that non-bipartite (0, 2)-graphs of valency k satisfy v ≤ 2^{k−1}.

The bipartite double has an involutory automorphism without fixed edges, namely the one interchanging x^{+} and x^{−} for each x. Conversely, given any bipartite (0, 2)-graph Δ with involutory automorphism σ without fixed edges that interchanges the two classes of the bipartition, one can construct a (0, 2)-graph Γ = Δ/σ that has the σ-orbits as vertices, where two σ-orbits are adjacent when there are edges between them.

In terms of semibiplanes, σ is a polarity without absolute points. This shows that there is a 1-1 correspondence between nonbipartite (0, 2)-graphs of valency k and semibiplanes of block size k with given polarity without absolute points.

Classifying (0, 2)-graphs of small valency is thus reduced to classifying semibiplanes of small block size, and finding their polarities.

The extended bipartite double of a graph Γ is obtained from the bipartite double by adding edges x^{−}x^{+} for each x. The extended bipartite double of a nonbipartite rectagraph is a bipartite rectagraph. The extended bipartite double of a bipartite graph Γ is just the product K_{2} × Γ.

The universal (0, 2)-cover of a (0, 2)-graph is its universal cover modulo 4-cycles. It is a (0, 2)-graph again, and is bipartite.

4 Products

Let us use the symbol ∼ to denote adjacency.

For graphs Γ and Δ, let Γ × Δ be the graph of which the vertex set is the Cartesian product of the vertex sets of Γ and Δ, where (x, y) ∼ (x′, y′) whenever either x = x′ and y ∼ y′ or x ∼ x′ and y = y′.

If Γ and Δ are (0, 2)-graphs, then also Γ × Δ is one. And if both are bipartite, then so is Γ × Δ. The valency of Γ × Δ is the sum of the valencies of Γ and Δ. The diameter of Γ × Δ is the sum of the diameters of Γ and Δ.

The hypercube 2^{k} (also called Q_{k}) is ×_{i=1}^{k}K_{2}.

5 Quotients

Let Γ be a graph and G a group of automorphisms of Γ. The quotient Γ/G is the graph that has as vertices the G-orbits on the vertex set of Γ, where two G-orbits are adjacent when they contain adjacent elements.

If Γ is a (0, 2)-graph and no two elements of any G-orbit are joined by a path of length 1, 2 or 4, then also Γ/G is a (0, 2)-graph.

In case G = ⟨σ⟩ we write Γ/σ instead of Γ/G.

For example, let Δ be the bipartitite double of the icosahedron (Δ_{5.2} in the tables below), and let Γ = 2^{2} × Δ. Then Γ has 96 vertices and valency 7 and group of order 3840. (It is Δ_{7.38}.) Let σ be the automorphism that sends each vertex to the unique vertex at distance 6. Then Γ/σ is bipartite, with 48 vertices, valency 7 and group of order 1920. (It is Δ_{7.2}.)

Let δ be the automorphism of Γ that interchanges (u, x^{+}) and (u, x^{−}) for all u and x. Then τ = σδ is an automorphism of Γ that sends each vertex to a vertex at distance 5, and Γ/τ is a nonbipartite rectagraph with 48 vertices, valency 7 and group of order 960. (It is Γ_{7.44}.)

6 Quotients of hypercubes

Let C be a linear code in 2^{k} viewed as binary vector space. If no distances 1, 2 or 4 occur between two code words, then the coset graph 2^{k}/C is a (0, 2)-graph of valency k. If moreover no distance 3 occurs (so that C has minimum distance at least 5), then 2^{k}/C is a rectagraph. If no odd weights occur, then 2^{k}/C is bipartite.

For example, with C = ⟨1110000, 0111111⟩, the code C has weights 0, 3, 5, 6 and the quotient 2^{7}/C is a (0, 2)-graph of valency 7 on 32 vertices, with automorphism group of order 1536 = 2!.4!.2^{5}. (It is Γ_{7.25}.)

Conversely, every rectagraph in which any 3-claw determines a unique 3-cube is a quotient of a hypercube (not necessarily a coset graph), and in particular has a number of vertices that is a power of two. For details, see [1], 4.3.6 and 4.3.8.

7 Nonbipartite quotients of a hypercube

Let Δ be the hypercube 2^{k}, with as vertices the binary vectors of length k. Its group of automorphisms is 2^{k} : Sym(k).

The involutions without fixed edges that interchange the two classes of the bipartition are the maps x ↦ π(x) + u, where π ∈ Sym(k) is a coordinate permutation of order 1 or 2 and u ∈ 2^{k} is a vector of odd weight, where π(u) = u, and π fixes at least three coordinates in the support of u.

(Indeed, if x ↦ π(x) + u has order 2, then x = π(π(x)) + π(u) + u for all x, so that π(u) = u and π^{2} = 1. The vector u must have odd weight to interchange the two classes of the bipartition. If there is a fixed edge (x, π(x) + u), then x + π(x) + u has weight 1, and π fixes a unique element of the support of u.)

The conjugacy classes of these involutions have representatives given by such maps x ↦ π(x) + u, where the support of u has odd weight at least 3, and is fixed pointwise by π.

(Indeed, choose the vector a so that the support of a + π(a) + u is fixed pointwise by π. Then x ↦ π(x + a) + u + a is the required conjugate.)

If π fixes a coordinate outside the support of u, then the resulting quotient is of the form 2 × E for some (0, 2)-graph E of valency k − 1. Hence, we may restrict ourselves to the case where π moves all positions outside the support of u. Now k is odd.

8 Nonbipartite quotients of a folded hypercube

If k is even, then the quotient 2^{k}/1, the folded k-cube, is still bipartite. The involutions without fixed edges that interchange the two classes of the bipartition are the maps x ↦ π(x) + u where π ∈ Sym(k) is a coordinate permutation of order 1 or 2 and u ∈ 2^{k} is a vector of odd weight, and either π(u) = u + 1, or π(u) = u where π fixes at least three coordinates inside and three coordinate outside the support of u.

In particular, for k = 6 we can use either π = 1, u = (000111) and find K_{4} × K_{4}, or π = (12)(34)(56), u = (010101) and find the Shrikhande graph.

9 Quotients of projective planes

Given a projective plane Π with involution σ, construct a semibiplane of which the points and blocks are the σ-orbits of size 2 on the points and blocks of Π (Hughes [2]). If Π has parameters P G(2, q) then for the incidence graph of the semibiplane one has k = q and one of: (i) v = q^{2} (elation, q even), (ii) v = q^{2} −1 (homology, q odd), (iii) v = q^{2} −\sqrt{q} (Baer involution, q square). There is work by Moorhouse [5] on reconstructing Π given the semibiplane Π/σ.

10 The half-double of a locally bipartite graph

Let Γ be a graph, and assume that for each vertex x a partition Π_{x} of the set of neighbours of Γ is given. Then we can define a graph Δ by taking as vertices the pairs (x, π) where π ∈ Π_{x}, and letting (x, π) be adjacent to (y, ρ) when y ∈ π and x ∈ ρ.

The resulting graph Δ has the same number as edges as Γ, and the covering map (x, π) ↦ x sends edges to edges.

Now let Γ be locally connected and locally bipartite, without vertices of valency 1. Then for each vertex x, the set of neighbours of x has a unique partition into two cocliques, and the above construction yields a graph Δ, called the half-double of Γ (with twice as many vertices and the same number of edges). Note that Δ need not be connected, even when Γ is.

Apply this construction to the strongly regular graph with parameters (v, k, λ) = (36, 14, 4) (with automorphism group U_{3}(3).2 and point stabiliser L_{2}(7).2) that is the first subconstituent of the Hall-Janko graph on 100 points. The result is a bipartite (0,2)-graph of diameter 5 and valency 7 on 72 vertices. Each vertex has distance 5 to a unique other point. Interchanging antipodes is not an automorphism, but identifying antipodes yields the graph Γ again. This graph has automorphism group U_{3}(3).2 with point stabilizer L_{2}(7). (It is Δ_{7.29}.)

11 A cover

Let us describe one more explicit construction of a bipartite (0, 2)-graph. It is a 2-cover of the extended bipartite double of K_{4} × K_{4} on 64 vertices with k = 7. Let the vertex set be A × A × B × B, where A = Z_{3} ∪ {∞} and B = Z_{2}. Let the adjacencies be (a, b, 0, j) ∼ (a, c, 1, j + f(a, b, c)) and (a, b, 0, j) ∼ (c, b, 1, j + f(b, a, c)) for a, b, c ∈ A and j ∈ B, where f(a, b, c) = 1 for a = ∞, b ≠ ∞, c = b − 1 or c = b, and for a ≠ ∞, b ≠ ∞, c = b + 1, and f(a, b, c) = 0 otherwise. The resulting graph has the stated properties. Its group is vertex transitive of order 1152. (It is Δ_{7.22}.)

12 A (0, 2)-graph from the dodecahedron

Consider the graph on the 20 vertices of the dodecahedron, adjacent when either adjacent on the dodecahedron, or at distance three joined by a path ”step, turn left, step, turn right, step”. (This latter relation is an equivalence relation, inducing 5K_{4}. Thus, the graph is the edgedisjoint union of the dodecahedron graph and 5K_{4}, each of valency 3.) The resulting graph is Γ_{6.8}.

13 Semibiplanes with k ≤ 7

We find unique bipartite (0, 2)-graphs of valency k for k ≤ 3, and 2, 4, 13, 40 nonisomorphic ones for k = 4, 5, 6, 7, respectively.

(A referee asks: ‘How?’. The short answer is: by computer search. Patric Östergård independently verified these numbers.)

In the table below, # gives a serial number (given k), d denotes the diameter, ‘bipd’ stands for bipartite double, ‘drg’ means distance-regular graph, ‘ico’ means icosahedron. The ‘distribution’ column gives the distance distribution: the number of points at each distance from a given point. If the group is nontransitive, there may be several different distributions, depending on the choice of the given point.

Viewed as semibiplanes, each of these graphs is self-dual, that is, all bipartite (0, 2)-graphs with 1 ≤ k ≤ 7 have an automorphism that interchanges the two classes of the bipartition. In particular, each has a nontrivial group of automorphisms G. The ‘gsz’ column gives |G|.

The bipartite (0, 2)-graph of valency k with serial number i is called Δ_{k.i}.

# k  v d distribution  gsz orbits  graph
1 0  1 0 1  1 tra  2^{0}
1 1  2 1 1+1  2 tra  2^{1}
1 2  4 2 1+2+1  8 tra  2^{2}
1 3  8 3 1+3+3+1  48 tra  2^{3}
1 4 14 3 1+4+6+3  336 tra  2-(7,4,2)
2 4 16 4 1+4+6+4+1  384 tra  2^{4}
1 5 22 3 1+5+10+6  1320 tra  2-(11,5,2)
2 5 24 4 1+5+10+7+1  480 tra  bipd(ico)
3 5 28 4 1+5+10+9+3  672 tra  2 × Δ_{4.1}
4 5 32 5 1+5+10+10+5+1  3840 tra  2^{5}
1 6 32 3 1+6+15+10  1536 tra  2-(16,6,2)
2 6 32 3 1+6+15+10  768 tra  2-(16,6,2)
3 6 32 3 1+6+15+10  23040 tra  2-(16,6,2), 2^{6}/1
4 6 36 4 1+6+15+12+2  96 12+24
5 6 36 4 1+6+15+12+2 4320 tra drg [3],[1, p.399]
6 6 36 4 1+6+15+12+2  48 12+24
7 6 40 4 1+6+15+14+4  48 8+8+24
8 6 40 4 1+6+15+14+4  120 tra
9 6 44 4 1+6+15+16+6 2640 tra 2 × Δ_{5.1}
10 6 48 5 1+6+15+18+8 (32x)  256 16+32

1+6+15+17+8+1 (16x)

11 6 48 5 1+6+15+17+8+1  960 tra  2 × Δ_{5.2}
12 6 56 5 1+6+15+19+12+3  2688 tra  2^{2} × Δ_{4.1}
13 6 64 6 1+6+15+20+15+6+1  46080 tra  2^{6}
1 7 48 4 1+7+21+17+2  384 tra
2 7 48 4 1+7+21+17+2 1920 tra Δ_{7.38}/σ, see §5
3 7 48 4 1+7+21+17+2  48 tra
4 7 48 4 1+7+21+17+2  64 16+32
5 7 48 4 1+7+21+17+2  64 16+32
6 7 48 4 1+7+21+17+2  48 tra
7 7 48 4 1+7+21+17+2  96 tra
8 7 48 4 1+7+21+17+2  72 12+36
9 7 48 4 1+7+21+17+2  96 tra
10 7 48 4 1+7+21+17+2 2016 tra Π/σ, see §9
11 7 56 4 1+7+21+21+6  16 2*4+2*8+2*16
12 7 56 4 1+7+21+21+6  8 4*4+5*8
13 7 56 4 1+7+21+21+6  16 2*4+2*8+2*16
14 7 56 4 1+7+21+21+6  24 2+6+4*12
15 7 56 4 1+7+21+21+6  8 4*4+5*8
16 7 56 4 1+7+21+21+6  4 14*4
17 7 56 4 1+7+21+21+6  16 3*8+2*16
18 7 64 4 1+7+21+25+10  48 16+48
19 7 64 4 1+7+21+25+10  120 24+40
20 7 64 4 1+7+21+25+10  3072 tra  2 × Δ_{6.1}
21 7 64 4 1+7+21+25+10  1536 tra  2 × Δ_{6.2}
22 7 64 4 1+7+21+25+10  1152 tra  see §11
23 7 64 4 1+7+21+25+10  46080 tra  2 × Δ_{6.3}
24 7 64 5 1+7+21+25+10 (60x)  12 4+5*12

1+7+21+24+10+1 (4x)

25 7 64 5 1+7+21+24+10+1 (36x)  24 4+5*12

1+7+21+25+10 (28x)

26 7 64 5 1+7+21+24+10+1 (24x)  8 8*4+4*8

1+7+21+25+10 (40x)

27 7 64 5 1+7+21+24+10+1 (14x)  12 2*2+2*6+4*12

1+7+21+25+10 (50x)

28 7 64 5 1+7+21+24+10+1 (8x)  336 8+56

# k  v d distribution  gsz orbits  graph

1+7+21+25+10 (56x)

29 7  72 5 1+7+21+28+14+1  12096 tra  U_{3}(3).2/L_{2}(7)
30 7  72 5 1+7+21+27+14+2  192 24+48  2 × Δ_{6.4}
31 7  72 5 1+7+21+27+14+2  8640 tra  2 × Δ_{6.5}
32 7  72 5 1+7+21+27+14+2  96 24+48  2 × Δ_{6.6}
33 7  80 5 1+7+21+30+18+3 (32x)  48 8+24+48

1+7+21+31+18+2 (48x)

34 7  80 5 1+7+21+29+18+4  96 16+16+48 2 × Δ_{6.7}
35 7  80 5 1+7+21+29+18+4  240 tra  2 × Δ_{6.8}
36 7  88 5 1+7+21+31+22+6  10560 tra  2^{2} × Δ_{5.1}
37 7  96 6 1+7+21+32+25+9+1 (32x)  512 32+64  2 × Δ_{6.10}

1+7+21+33+26+8 (64x)

38 7  96 6 1+7+21+32+25+9+1  3840 tra  2^{2} × Δ_{5.2}
39 7 112 6 1+7+21+34+31+15+3  16128 tra  2^{3} × Δ_{4.1}
40 7 128 7 1+7+21+35+35+21+7+1  645120 tra  2^{7}

The above table contains five pairs of graphs for which identical data is given. Given a vertex x of a (0, 2)-graph Γ with set of neighbours A, we can identify a vertex y at distance 2 from x with a pair of vertices (”edge”) on A. Given a vertex z at distance 3 from x, the union of the geodesics from z to x determines a graph on a subset of A that is regular of valency 2, that is, a union of polygons.

For graphs Δ_{7.i} with 1 ≤ i ≤ 10 of valency 7 on 48 vertices, for each vertex x the number of vertices z at distance 3 from x that determine 2K_{3} equals 2, 10, 5, 6, 2, 7, 4, 6 or 7, 8, 7, respectively. This suffices to distinguish them. (They can also be distinguished by looking at their nonbipartite quotients.)

For graphs Δ_{7.i} with 11 ≤ i ≤ 17 of valency 7 on 56 vertices, for each vertex x the number of vertices z at distance 3 from x that determine K_{3} equals 0/1, 0/1/2/3, 0/1/2, 0/1/3, 0/1, 0/1/2, 0/1, respectively, where / abbreviates ”or” (and all alternatives do occur). This suffices to distinguish them.

Of the graphs given here only Δ_{6.3}, Δ_{7.2}, and Δ_{7.23} are not their own universal (0, 2)-cover. (Their universal (0, 2)-covers are 2^{6}, Δ_{7.38} and 2^{7}, respectively.)

14 Nonbipartite (0, 2)-graphs with k ≤ 7

The nonbipartite (0, 2)-graphs with k ≤ 7 have bipartite doubles found above. We find 1, 1, 4, 11, 56 nonisomorphic solutions for k = 3, 4, 5, 6, 7, respectively.

The column ‘locally’ describes the local graph by a string of digits giving the component sizes (each component is either a single point or a cycle). For example, the C31 for K_{2} × K_{4} means that all local graphs are the union of a triangle and an isolated vertex. (The C is just to remind the reader that what follows is a digit string, not a number.) A rectagraph does not have triangles, so all components of local graphs are single points, and we write ‘recta’ instead of C111..1. In cases where this is an automorphism, ϕ denotes the interchange of antipodal vertices.

The nonbipartite (0, 2)-graph of valency k with serial number i is called Γ_{k.i}.

# bipd k  v d distribution  locally  gsz orbits graph
1  3.1 3  4 1 1+3  C3  24 tra  2^{3}/(111) ≅ K_{4}
1  4.2 4  8 2 1+4+3  C31  48 tra  2^{4}/(0111) ≅ K_{2} × K_{4}
1  5.2 5 12 3 1+5+5+1  C5  120 tra  icosahedron
2  5.4 5 16 2 1+5+10  recta  1920 tra  2^{5}/(11111)
3  5.4 5 16 3 1+5+7+3  C311  192 tra  2^{5}/(00111) ≅ 2^{2} × K_{4}
4  5.4 5 16 3 1+5+7+3 (8x) C311  96 8+8  2^{5}/π_{(12)}(00111)
1+5+10 (8x)  C11111
1  6.3 6 16 2 1+6+9  C33  1152 tra  K_{4} × K_{4}
2  6.3 6 16 2 1+6+9  C6  192 tra  Shrikhande

# bipd k  v d distribution  locally  gsz orbits  graph
3  6.8 6 20 3 1+6+12+1  C3111  60 tra  §12
4  6.7 6 20 3 1+6+10+3 (12x)  C51  24 4+4+12
1+6+9+4 (4x)  C6
1+6+12+1 (4x)  C3111
5 6.11 6 24 3 1+6+12+5 (16x) C3111 32 8+16
1+6+15+2 (8x)  C111111
6 6.11 6 24 3 1+6+15+2  recta  480 tra  (2 × bipd(ico))/ϕ
7 6.11 6 24 4 1+6+10+6+1  C51  240 tra  2 × Γ_{5.1}
8 6.12 6 28 3 1+6+12+9 (16x)  C3111  48 4+12+12
1+6+15+6 (12x)  C111111
9 6.13 6 32 3 1+6+15+10  recta  3840 tra  2 × Γ_{5.2}
10 6.13 6 32 4 1+6+12+10+3  C3111  1152 tra  2^{3} × K_{4}
11 6.13 6 32 4 1+6+12+10+3 (16x) C3111  192 16+16  2 × Γ_{5.4}
1+6+15+10 (16x)  C111111
1  7.1 7 24 2 1+7+16  C511  96 tra
2  7.1 7 24 2 1+7+16  C511  96 tra
3  7.2 7 24 2 1+7+16  C511  480 tra
4  7.2 7 24 2 1+7+16  C511  480 tra
5  7.1 7 24 3 1+7+15+1  C331  96 tra
6  7.2 7 24 3 1+7+15+1  C61  48 tra
7  7.4 7 24 3 1+7+14+2 (4x)  C7  8 4*4+8
1+7+15+1 (16x)  C61
1+7+16 (4x)  C511
8 7.5 7 24 3 1+7+14+2 (8x) C7 16 8+8+8
1+7+15+1 (8x)  C61
1+7+16 (8x)  C511
9 7.6 7 24 3 1+7+16 (4x) C511 4 6*4
1+7+15+1 (16x)  C61
1+7+14+2 (4x)  C7
10 7.8 7 24 3 1+7+14+2 (12x) C7 12 4*6
1+7+15+1 (12x)  C61
11 7.9 7 24 3 1+7+16 (12x) C511 12 4*6
1+7+15+1 (12x)  C61
12 7.10 7 24 3 1+7+14+2  C7  336 tra  drg [1, p.386]
13 7.24 7 32 3 1+7+18+6 (12x)  C31111  6 2+5*6
1+7+16+8 (12x)  C511
1+7+15+9 (6x)  C61
1+7+21+3 (2x)  C1111111
14 7.26 7 32 3 1+7+18+6 (8x) C31111 4 8*2+4*4
1+7+21+3 (4x)  C1111111
1+7+16+8 (14x)  C511
1+7+15+9 (2x)  C331
1+7+15+9 (2x)  C61
1+7+14+10 (2x)  C7
15 7.27 7 32 3 1+7+21+3 (3x) C1111111 2 8*1+12*2
1+7+16+8 (13x)  C511
1+7+18+6 (10x)  C31111
1+7+14+10 (1x)  C7
1+7+15+9 (4x)  C61
1+7+15+9 (1x)  C331
16 7.18 7 32 3 1+7+16+8 (24x) C511 8 4*8
1+7+15+9 (8x)  C61
17 7.18 7 32 3 1+7+18+6  C31111  24 8+24
18 7.20 7 32 3 1+7+18+6  C31111  512 tra
19 7.20 7 32 3 1+7+18+6  C31111  256 tra
20 7.21 7 32 3 1+7+18+6  C31111  96 tra
21 7.21 7 32 3 1+7+18+6  C31111  768 tra
22 7.28 7 32 3 1+7+21+3 (4x)  C1111111  24 4+4+24

# bipd k  v d distribution  locally  gsz orbits  graph
1+7+18+6 (24x)  C31111
1+7+15+9 (4x)  C331
23 7.28 7 32 3 1+7+21+3 (4x) C1111111 168 4+28
1+7+15+9 (28x)  C61
24 7.22 7 32 3 1+7+16+8 (24x) C511 48 8+24
1+7+15+9 (8x)  C61
25 7.23 7 32 3 1+7+18+6  C31111  1536 tra  2^{7}/C, see §6
26 7.23 7 32 3 1+7+18+6  C31111  256 tra
27 7.23 7 32 3 1+7+15+9  C331  2304 tra  2 × Γ_{6.1}
28 7.23 7 32 3 1+7+15+9  C61  384 tra  2 × Γ_{6.2}
29 7.25 7 32 4 1+7+16+7+1 (6x)  C511  12 2+5*6
1+7+16+8 (12x)  C511
1+7+14+9+1 (6x)  C7
1+7+18+6 (8x)  C31111
30 7.28 7 32 4 1+7+14+9+1 (4x) C7 56 4+28
1+7+16+8 (28x)  C511
31 7.30 7 36 3 1+7+18+10 (20x) C31111 32 4+2*8+16
1+7+21+7 (16x)  C1111111
32 7.32 7 36 3 1+7+18+10 (20x) C31111 8 3*4+3*8
1+7+21+7 (16x)  C1111111
33 7.34 7 40 4 1+7+16+13+3 (24x) C511 48 8+8+24 2 × Γ_{6.4}
1+7+15+13+4 (8x)  C61
1+7+18+13+1 (8x)  C31111
34 7.34 7 40 4 1+7+18+12+2 (8x) C31111 16 3*8+16
1+7+18+14 (16x)  C31111
1+7+21+11 (16x)  C1111111
35 7.35 7 40 4 1+7+21+11 (16x) C1111111 8 5*8
1+7+18+14 (16x)  C31111
1+7+18+12+2 (8x)  C31111
36 7.35 7 40 4 1+7+18+13+1  C31111  120 tra  2 × Γ_{6.3}
37 7.36 7 44 3 1+7+18+18 (20x)  C31111  80 4+20+20
1+7+21+15 (24x)  C1111111
38 7.37 7 48 4 1+7+21+19 (16x) C1111111 32 3*16
1+7+18+20+2 (16x)  C31111
1+7+21+17+2 (16x)  C1111111
39 7.37 7 48 4 1+7+18+17+5 (8x) C31111 32 4*8+16
1+7+21+16+3 (8x)  C1111111
1+7+18+18+4 (8x)  C31111
1+7+21+17+2 (24x)  C1111111
40 7.37 7 48 4 1+7+18+17+5 (16x) C31111 128 16+32
1+7+21+17+2 (32x)  C1111111
41 7.38 7 48 4 1+7+18+17+5 (32x) C31111 64 16+32 2 × Γ_{6.5}
1+7+21+17+2 (16x)  C1111111
42 7.38 7 48 4 1+7+18+19+3 (24x) C31111 96 24+24
1+7+21+19 (24x)  C1111111
43 7.38 7 48 4 1+7+18+19+3 (16x) C31111 64 3*16
1+7+21+16+3 (16x)  C1111111
1+7+21+19 (16x)  C1111111
44 7.38 7 48 4 1+7+21+16+3  recta  960 tra  Δ_{7.38}/τ, see §5
45 7.38 7 48 4 1+7+21+17+2  recta  960 tra  2 × Γ_{6.6}
46 7.38 7 48 5 1+7+16+16+7+1  C511  960 tra  2^{2} × Γ_{5.1}
47 7.38 7 48 5 1+7+16+16+7+1 (24x) C511  480 24+24
1+7+21+16+3 (24x)  C1111111
48 7.39 7 56 4 1+7+18+21+9 (32x) C31111 96 8+24+24 2 × Γ_{6.8}
1+7+21+21+6 (24x)  C1111111
49 7.39 7 56 4 1+7+18+21+9  C31111  8064 tra  K_{4} × Δ_{4.1}
50 7.39 7 56 4 1+7+18+21+9 (24x)  C31111  384 8+16+32
1+7+21+24+3 (32x)  C1111111

# bipd k  v d distribution  locally  gsz orbits  graph
51 7.40 7 64 3 1+7+21+35  recta  322560 tra  2^{7}/(1111111)
52 7.40 7 64 4 1+7+21+25+10  recta  15360 tra  2^{2} × Γ_{5.2}
53 7.40 7 64 4 1+7+21+25+10 (32x)  recta  7680 32+32  2^{7}/π_{(12)}·
1+7+21+35 (32x)  ·(0011111)
54 7.40 7 64 5 1+7+18+22+13+3  C31111  9216 tra  2^{4} × K_{4}
55 7.40 7 64 5 1+7+18+22+13+3 (32x) C31111  768 32+32  2^{2} × Γ_{5.4}
1+7+21+25+10 (32x)  C1111111
56 7.40 7 64 5 1+7+18+22+13+3 (16x) C31111  768 2*16+32 2^{7}/π_{(12)(34)}·
1+7+21+25+10 (32x) C1111111 ·(0000111)
1+7+21+35 (16x)  C1111111

The above table contains two pairs of graphs on 24 points for which identical data is given. All four have local graphs C511, so that in each the edges that occur in a triangle form two disjoint icosahedra, and the remaining edges, two on each point, join that point to two antipodal vertices in the other icosahedron. The structure is that of two icosahedra together with a matching of the six antipodal pairs of one with the six antipodal pairs of the other. One sees that there are four possibilities for the number of induced 2 × K_{3} on each edge across, namely 3, 2, 5, 0 for the for cases Γ_{7.i}, i = 1, 2, 3, 4, respectively.

References

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

[2] D. R. Hughes, Biplanes and semi-biplanes, in: Combinatorial mathematics (Proc. Internat. Conf. Combinatorial Theory, Australian Nat. Univ., Canberra, 1977), pp. 55–58, Lecture Notes in Math. 686, Springer, Berlin, 1978.

[3] Zvonimir Janko & Tran Van Trung, Two new semibiplanes, J. Combin. Theory Ser. A 33 (1982) 102–105.

[4] Michel Mollard, Table of (0,2)-graphs of order less than 32, Rapport de Recherche/IMAG RR 939, Grenoble, June 1994.

[5] G. Eric Moorhouse, Reconstructing projective planes from semibiplanes, in: Coding theory and design theory, Part II, pp. 280–285, IMA Vol. Math. Appl. 21, Springer, New York, 1990.

[6] H. M. Mulder, The interval function of a graph, PhD thesis, Vrije Universiteit Amsterdam, 1980.

[7] A. Neumaier, Rectagraphs, diagrams, and Suzuki’s sporadic simple group, in: Algebraic and geometric combinatorics, pp. 305–318, North-Holland Math. Stud. 65, North-Holland, Amsterdam, 1982.

[8] P. R. Wild, On semibiplanes, Ph.D. Thesis, University of London, 1980.

[9] Peter Wild, Generalized Hussain graphs and semibiplanes with k ≤ 6, Ars Combin. 14 (1982) 147–167.