Classification of the (0,2)-graphs of valency 8

Andries E. Brouwer & Patric R. J. Östergård

December 14, 2006

Abstract

We find the 302 graphs of valency 8 with the property that any two nonadjacent vertices have 0 or 2 common neighbours, and, in particular, the 104 semibiplanes of block size 8.

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).

Martyn Mulder [10] 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.

Peter Wild [13] determined all semibiplanes of block size at most 6. Michel Mollard [8] determined all (0, 2)-graphs on at most 31 vertices (and finds that these have valency at most 7). Andries Brouwer [1] determined all (0, 2)-graphs with valency at most 7.

In this note we find all (0, 2)-graphs with valency 8. It turns out that the total number N(k) of nonisomorphic (0, 2)-graphs with k ≤ 8 is given by

\begin{matrix}k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ N(k) & 1 & 1 & 1 & 2 & 3 & 8 & 24 & 96 & 302 \end{matrix}

2 Classification algorithms

Reduction to the bipartite case

We first classify the bipartite (0, 2)-graphs with given valency k. Given that classification, the nonbipartite (0, 2)-graphs of that valency are easily found by observing that any nonbipartite (0, 2)-graph Γ produces a bipartite (0, 2)-graph Γ′ with the same valency when the following doubling construction is applied: For each vertex x in Γ, there are two vertices x^{+}, x^{−} in Γ′ and for each edge xy in Γ, there are two edges x^{+}y^{−}, x^{−}y^{+} in Γ′. This graph Γ′ (known as the bipartite double of Γ) has an automorphism σ of order two without fixed edges interchanging x^{+} and x^{−}. And conversely, given any bipartite (0, 2)-graph Δ with an automorphism of order 2 without fixed edges that interchanges the two classes of the bipartition, the quotient Δ/σ will be a nonbipartite (0, 2)-graph. In this way the entire classification is reduced to the bipartite case.

Classification in the bipartite case

In the classification, we first fix one vertex, u, and then for increasing d build up graphs with vertices at distance at most d from u that fulfill some necessary conditions for being an induced subgraph of a bipartite (0,2)-graph with given valency k.

Let S_{i} = {x : d(x, u) = i}. Clearly |S_{1}| = k, and we let S_{1} = {1, 2, …, k}. For i > 1, we may denote any element v of S_{i} by {w : w ∈ S_{i−1} ∩ N(v)}, where N(v) is the neighborhood of v. (This works, since S_{i−1} ∩ N(v) ≠ S_{i−1} ∩ N(v′) for any distinct v, v′ ∈ S_{i}. Indeed, this is clear for i = 2, and follows from |S_{i−1} ∩ N(v)| ≥ i for i > 2.)

Since every vertex in S_{2} has at least one common neighbor with u, it must have exactly two neighbors in S_{1}. Moreover, since every two distinct vertices in S_{1} have u as a neighbor, they must have exactly one neighbor in S_{2}. Consequently, S_{2} = {{i, j} : 1 ≤ i < j ≤ k}, and we may view the elements of S_{2} as the edges of a complete graph of order k.

We now consider the case where, for some i ≥ 2, we have built up a graph with vertices at distance at most i from u, and try to find the vertices in S_{i+1}. Such an extension consists of two steps: finding candidates for vertices in S_{i+1}—more precisely, we determine possible neighborhoods in S_{i} for such a vertex—and finding a subset of candidates that form S_{i+1}. We will now have a closer look at these two steps. Throughout the search, necessary conditions for the complete graph to be a (0, 2)-graph are used for pruning.

In finding candidates for vertices in S_{i+1} we focus on the fact that a vertex in S_{i+1} and a vertex in S_{i−1} should have either 0 or 2 common neighbors in S_{i}. We therefore say that a set of vertices v_{1}, v_{2}, …, v_{m} ∈ S_{i} forms a candidate if ∪_{i=1}^{m}v_{i} as a multiset contains each element of S_{i−1} 0 or 2 times and m ≤ k. Such candidates can be found by backtrack search: A partial candidate should cover the elements of S_{i−1} 0, 1, or 2 times; one may prune the search if the number of elements covered once exceeds the number of distinct elements that can be covered by the vertices in S_{i} still to be added (utilizing the fact that m ≤ k and knowing the maximum size of any set v_{i}).

Determining the candidates for vertices in S_{3}, where the actual computer search starts, has a nice interpretation in terms of graphs of order k (when the vertices in S_{2} are interpreted as the edges in the complete graph of order k). Namely, the candidates then correspond to the 2-regular graphs with vertices from {1, 2, …, k}. Such graphs clearly consist of sets of cycles and their isomorphism classes can be characterized by the length of the cycles. For k = 8, considered in this study, they are

4 + 4, 5 + 3, 8, 4 + 3, 7, 3 + 3, 6, 5, 4, 3.  (1)

(From now on, we occasionally consider the specific case k = 8 for clarity. However, all ideas can be applied for arbitrary k.)

In searching for subsets of candidates that form S_{i+1} we focus on the fact that two distinct vertices in S_{i} should have either 0 or 2 common neighbors. Now we know their common neighbors in S_{i−1}; if this number is 0, 1, or 2, then the pair of vertices should occur in the neighborhood of 0 or 2, 1, or 0 vertices in S_{i+1}, respectively. In the last of these three cases, we can immediately reject corresponding candidates. It is not straightforward to implement the requirement in the first of the cases in a computer search, so the core of the algorithm is to search for candidates that cover the pairs of vertices in S_{i} with exactly one common neighbor in S_{i−1} exactly once. In fact, we then have instances of the exact cover problem [6].

Checking the requirement that two vertices of S_{i} that do not have common neighbors in S_{i−1} must have 0 or 2 common neighbors in S_{i+1} cannot—for efficiency reasons—be postponed until the solutions of the aforementioned exact cover problem are found. Terming a vertex saturated if its valency is k, whenever a vertex v ∈ S_{i} gets saturated when building up S_{i+1} with the exact cover algorithm, we carry out this pruning test for all pairs in S_{i} where v is one of the vertices.

All solutions of the exact cover problem with the additional pruning test are immediately subjected to one more test: two vertices in S_{i+1} cannot have more than 2 common neighbors in S_{i}.

To make the outlined algorithm efficient enough for settling the case k = 8 in reasonable time, we need to incorporate isomorph rejection in some form. This is done during the search for S_{3}, which is the hardest part of this classification problem. The search for S_{3} is divided into ten parts, corresponding to the cycle types (1). Numbering these types from 1 to 10, in part i ∈ {1, 2, …, 10} of the search the first vertex has type i (there is a unique choice, up to isomorphism) and the type of the other vertices must be greater than or equal to i. The ordering of the types is of great importance; the ordering in (1), in increasing order with respect to the value of i, works reasonably well.

For each of the aforementioned ten parts, S_{3} is constructed in two steps. Consider a neighbor v in S_{2} of the vertex that is fixed first (the choice of v will occasionally have some—but not a crucial—impact on the performance). Then we first determine all vertices in S_{3} that have v as a neighbor. During and after this search partial solutions are also subjected to isomorphism tests, using nauty [7]. From there on, we search for the rest of S_{3} with the approach outlined earlier.

Solutions for S_{i} with i ≥ 4 can be obtained directly by the described algorithm. Finally, isomorph rejection has to be carried out among the complete (0, 2)-graphs.

Classification results

Whereas the classification of (0, 2)-graphs with valency 7 using the outlined algorithm takes only minutes of CPU time on a contemporary personal computer, the classification for valency 8 takes about one month. Below we present the main parameters of the graphs obtained and discuss some of their properties.

Actually, not all of the classification was done by computer. Some parts of extending (the unique) S_{3} obtained in case 10 to a complete (0, 2)-graph turned out to be computationally challenging. Fortunately, however, this is precisely the case that is well-understood. We have a rectagraph of valency k such that any 3-claw determines a unique 3-cube. By [2, 4.3.6, 4.3.8], the graph is a quotient of a hypercube. That means that the vertices of the graph can be labeled with binary words of length 8, where the set of words at each vertex has even minimum distance larger than 6, that is, 8. Up to equivalence there are two such codes, the trivial one-word code and the repetition code, and consequently two such graphs (since twists cannot occur), the 8-cube on 256 vertices, and its antipodal quotient on 128 vertices.

To get confidence in the validity of these computational results, we carried out double counting tests described in [5, Sect. 10.3]. Specifically, for each graph obtained, we determined its induced subgraphs consisting of one vertex and the vertices at distance at most 3, and calculated analytically the number of times the complete graph should have been produced (this is possible since from S_{3} onwards, no isomorph rejection is carried out before the graph is completed). We have to take into account though the missing computational results in case 10. Similar double counting was also carried out in the construction of S_{3}.

3 Semibiplanes with k = 8

The number N(k) of nonisomorphic bipartite (0, 2)-graphs with k ≤ 8 is given in the following table.

\begin{matrix}k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ N(k) & 1 & 1 & 1 & 1 & 2 & 4 & 13 & 40 & 104 \end{matrix}

In the table below, # gives a serial number (given k), d denotes the diameter, ‘bipd’ stands for bipartite double, ‘ebipd’ for extended 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. The ‘gsz’ column gives the size of the automorphism group G.

The ’graph’ column may give a construction or comment. In the case of quotients 2^{8}/C the code C is given by generators; a vector like 11100000 is abbreviated 1^{3}0^{5}.

All semibiplanes with block size k are self-dual for 1 ≤ k ≤ 7, but for k = 8 there are 15 non-self-dual examples, and non-selfduality is noted in the comments.

The bipartite (0, 2)-graph of valency k with serial number i is called Δ_{k.i}. Serial numbers for k ≤ 7 are as in [1].

Graph Δ_{8.2} is the quotient Π/σ, where Π is the projective plane P G(2, 8) and σ an elation, and the quotient is the semibiplane consisting of the σ-orbits of size 2 on points and lines. It is a distance-regular graph with parameters drg(8,7,6,1; 1,2,7,8), cf. [2, p. 224].

In some cases the second largest eigenvalue λ_{2} is given, in order to distinguish parameter sets that would otherwise have identical data.

#  v d distribution  gsz orbits  graph
1 64 4 1+8+28+24+3  384 tra
2 64 4 1+8+28+24+3  10752 tra  Π/σ, drg
3 68 4 1+8+28+26+5  4 17*4  λ_{2} = 3.708
4 68 4 1+8+28+26+5  20 2*4+3*20  λ_{2} = 3.689
5 68 4 1+8+28+26+5  4 17*4  λ_{2} = 3.755
6 68 4 1+8+28+26+5  20 2*4+3*20  λ_{2} = 3.742
7 72 4 1+8+28+28+7  144 tra
8 74 5 1+8+28+28+8+1 (18x)  672 2+16+56

1+8+28+29+8 (56x)

9 80 4 1+8+28+32+11  4 8*2+16*4  not selfdual
10 80 4 1+8+28+32+11  20 4*20  not selfdual
11 80 4 1+8+28+32+11  20 4*20
12 80 4 1+8+28+32+11  384 32+48
13 80 5 1+8+28+31+11+1  3840 tra  cf. §5.2, 5.6
14 80 5 1+8+28+31+11+1 (8x)  12 2*4+6*12  not selfdual

1+8+28+32+11 (72x)

15 80 5 1+8+28+31+11+1 (16x)  768 16+64

1+8+28+32+11 (64x)

16 84 4 1+8+28+34+13  16 4+6*8+2*16
17 84 4 1+8+28+34+13  64 4+16+2*32
18 84 4 1+8+28+34+13  32 4+2*8+2*16+32
19 84 4 1+8+28+34+13  1344 tra  cf. §5.4
20 84 5 1+8+28+33+13+1 (8x)  8 7*4+7*8  λ_{2} = 4.243

1+8+28+34+13 (76x)

21 84 5 1+8+28+33+13+1 (8x) 8 7*4+7*8 λ_{2} = 4.321

1+8+28+34+13 (76x)

22 84 5 1+8+28+33+13+1 (8x) 4 14*2+14*4 not selfdual

1+8+28+34+13 (76x)

23 84 5 1+8+28+33+13+1 (4x) 4 14*2+14*4 not selfdual

1+8+28+34+13 (80x)

24 84 5 1+8+28+33+13+1 (20x)  16 4+6*8+2*16

1+8+28+34+13 (64x)

25 84 5 1+8+28+33+13+1 (28x)  16 3*4+3*8+3*16

1+8+28+34+13 (56x)

26 84 5 1+8+28+33+13+1 (52x)  64 4+16+2*32

1+8+28+34+13 (32x)

27 84 5 1+8+28+33+13+1 (8x)  16 3*4+3*8+3*16

1+8+28+34+13 (76x)

#  v d distribution  gsz orbits  graph
28  84 5 1+8+28+33+13+1 (20x)  64 4+16+2*32

1+8+28+34+13 (64x)

29 84 5 1+8+28+33+13+1 (36x) 96 12+24+48

1+8+28+34+13 (48x)

30  88 4 1+8+28+36+15  160 8+40+4
31  88 5 1+8+28+35+15+1 (16x)  16 3*8+4*16

1+8+28+36+15 (72x)

32 88 5 1+8+28+35+15+1 (32x) 32 3*8+2*32

1+8+28+36+15 (56x)

33  96 4 1+8+28+40+19  1152 tra
34  96 5 1+8+28+37+19+3  5760 tra  ebipd(Γ_{7.44})
35  96 5 1+8+28+37+19+3 (64x)  384 32+64

1+8+28+40+19 (32x)

36  96 5 1+8+28+39+19+1  24 2*12+3*24
37  96 5 1+8+28+38+19+2  768 tra  2 × Δ_{7.1}
38  96 5 1+8+28+38+19+2  3840 tra  2 × Δ_{7.2}, ebipd(Γ_{7.45})
39  96 5 1+8+28+38+19+2  192 tra  2 × Δ_{7.9}
40  96 5 1+8+28+38+19+2  128 32+64  2 × Δ_{7.4}
41  96 5 1+8+28+38+19+2  128 32+64  2 × Δ_{7.5}
42  96 5 1+8+28+38+19+2  96 tra  2 × Δ_{7.6}
43  96 5 1+8+28+38+19+2  144 24+72  2 × Δ_{7.8}
44  96 5 1+8+28+38+19+2  192 tra  2 × Δ_{7.7}
45  96 5 1+8+28+38+19+2  96 tra  2 × Δ_{7.3}
46  96 5 1+8+28+38+19+2 (64x)  128 32+64

1+8+28+40+19 (32x)

47 96 5 1+8+28+38+19+2 (12x) 12 12*6+2*12 not selfdual

1+8+28+39+19+1 (48x) 1+8+28+40+19 (36x)

48 96 5 1+8+28+38+19+2 (12x) 24 8*12 not selfdual

1+8+28+39+19+1 (48x) 1+8+28+40+19 (36x)

49 96 5 1+8+28+39+19+1 (48x) 48 4*24 not selfdual

1+8+28+40+19 (48x)

50  96 5 1+8+28+39+19+1  96 48+48
51  96 5 1+8+28+39+19+1  72 24+36+36
52  96 5 1+8+28+38+19+2  4032 tra  2 × Δ_{7.10}
53 100 5 1+8+28+39+21+3 (24x)  2 28*1+36*2  not selfdual

1+8+28+40+21+2 (46x) 1+8+28+41+21+1 (26x) 1+8+28+42+21 (4x)

54 100 5 1+8+28+39+21+3 (16x)  4 25*4

1+8+28+40+21+2 (56x) 1+8+28+41+21+1 (24x) 1+8+28+42+21 (4x)

55 100 5 1+8+28+38+21+4 (2x) 2 22*1+39*2 not selfdual

1+8+28+39+21+3 (4x) 1+8+28+40+21+2 (32x) 1+8+28+41+21+1 (54x) 1+8+28+42+21 (8x)

56 100 5 1+8+28+39+21+3 (36x)  8 4*2+5*4+9*8

1+8+28+40+21+2 (40x) 1+8+28+41+21+1 (14x) 1+8+28+42+21 (10x)

57 100 5 1+8+28+40+21+2 (40x)  20 5*20

1+8+28+41+21+1 (40x) 1+8+28+42+21 (20x)

58 104 5 1+8+28+38+23+6 (8x)  32 3*8+3*16+32

1+8+28+39+23+5 (8x)

#  v d distribution  gsz orbits  graph

1+8+28+40+23+4 (32x) 1+8+28+41+23+3 (16x) 1+8+28+42+23+2 (40x)

59 104 5 1+8+28+40+23+4 (8x)  48 8+4*24

1+8+28+42+23+2 (96x)

60 104 5 1+8+28+38+23+6 (12x)  96 4+12+16+24+48

1+8+28+40+23+4 (52x) 1+8+28+42+23+2 (24x) 1+8+28+43+23+1 (16x)

61 104 5 1+8+28+40+23+4 (64x)  1536 16+24+64

1+8+28+42+23+2 (24x) 1+8+28+44+23 (16x)

62 112 4 1+8+28+48+27  21504 tra  cf. §5.5
63 112 5 1+8+28+42+27+6  16 4*8+5*16  2 × Δ_{7.12}
64 112 5 1+8+28+42+27+6  16 4*8+5*16  2 × Δ_{7.15}
65 112 5 1+8+28+42+27+6  48 4+12+4*24  2 × Δ_{7.14}
66 112 5 1+8+28+42+27+6  32 3*16+2*32  2 × Δ_{7.17}
67 112 5 1+8+28+42+27+6  32 2*8+2*16+2*32  2 × Δ_{7.11}
68 112 5 1+8+28+42+27+6  32 2*8+2*16+2*32  2 × Δ_{7.13}
69 112 5 1+8+28+42+27+6  8 14*8  2 × Δ_{7.16}
70 116 6 1+8+28+42+28+8+1 (4x)  672 4+28+84

1+8+28+46+29+4 (112x)

71 128 4 1+8+28+56+35  5160960 tra  2^{8}/1, ebipd(Γ_{7.51})
72 128 5 1+8+28+46+35+10  12288 tra  2^{2} × Δ_{6.1}
73 128 5 1+8+28+46+35+10  6144 tra  2^{2} × Δ_{6.2}
74 128 5 1+8+28+46+35+10  184320 tra  2^{2} × Δ_{6.3}, ebipd(Γ_{7.52})
75 128 5 1+8+28+46+35+10 (64x)  92160 64+64  2^{8}/π_{(12)}(00111111),
1+8+28+56+35 (64x)  ebipd(Γ_{7.53})
76 128 5 1+8+28+46+35+10  96 32+96  2 × Δ_{7.18}
77 128 5 1+8+28+46+35+10  2304 tra  2 × Δ_{7.22}
78 128 5 1+8+28+46+35+10  240 48+80  2 × Δ_{7.19}
79 128 6 1+8+28+45+34+11+1 (48x)  16 8*8+4*16  2 × Δ_{7.26}

1+8+28+46+35+10 (80x)

80 128 6 1+8+28+45+34+11+1 (72x) 48 8+5*24 2 × Δ_{7.25}

1+8+28+46+35+10 (56x)

81 128 6 1+8+28+45+34+11+1 (8x) 24 8+5*24 2 × Δ_{7.24}

1+8+28+46+35+10 (120x)

82 128 6 1+8+28+45+34+11+1 (28x) 24 2*4+2*12+4*24 2 × Δ_{7.27}

1+8+28+46+35+10 (100x)

83 128 6 1+8+28+45+34+11+1 (16x) 672 16+112 2 × Δ_{7.28}

1+8+28+46+35+10 (112x)

84 128 6 1+8+28+48+34+8+1 (24x) 384 16+2*24+64 not selfdual

1+8+28+48+35+8 (24x) 1+8+28+49+35+7 (64x) 1+8+28+52+35+4 (16x)

85 128 6 1+8+28+48+34+8+1 (2x)  48 2+6+8+16+2*48 not selfdual

1+8+28+48+35+8 (6x) 1+8+28+49+35+7 (112x) 1+8+28+50+35+6 (8x)

86 128 6 1+8+28+48+34+8+1 (8x) 64 2*8+16+32+64 not selfdual

1+8+28+48+35+8 (24x) 1+8+28+49+35+7 (64x) 1+8+28+50+35+6 (32x)

87 128 6 1+8+28+48+34+8+1 (16x) 512 2*16+32+64 not selfdual

1+8+28+48+35+8 (32x) 1+8+28+49+35+7 (64x) 1+8+28+52+35+4 (16x)

88 128 6 1+8+28+48+34+8+1 (56x)  10752 8+56+64  not selfdual

#  v d distribution  gsz orbits  graph

1+8+28+49+35+7 (64x) 1+8+28+56+35 (8x)

89 132 6 1+8+28+47+36+11+1 (8x)  16 9*4+8*8+2*16

1+8+28+48+36+10+1 (8x) 1+8+28+47+37+11 (12x) 1+8+28+48+37+10 (20x) 1+8+28+49+37+9 (36x) 1+8+28+50+37+8 (48x)

90 132 6 1+8+28+48+36+10+1 (36x)  72 2*12+36+72

1+8+28+50+36+8+1 (12x) 1+8+28+49+37+9 (72x) 1+8+28+50+37+8 (12x)

91 144 6 1+8+28+48+41+16+2  384 48+96  2^{2} × Δ_{6.6}
92 144 6 1+8+28+48+41+16+2  768 48+96  2^{2} × Δ_{6.4}
93 144 6 1+8+28+48+41+16+2  34560 tra  2^{2} × Δ_{6.5}
94 144 6 1+8+28+49+42+15+1  24192 tra  2 × Δ_{7.29}
95 160 6 1+8+28+50+47+22+4  384 32+32+96  2^{2} × Δ_{6.7}
96 160 6 1+8+28+50+47+22+4  960 tra  2^{2} × Δ_{6.8}
97 160 6 1+8+28+51+48+21+3 (64x)  96 16+48+96  2 × Δ_{7.33}

1+8+28+52+49+20+2 (96x)

98 164 6 1+8+28+50+48+24+5 (20x)  512 4+2*16+2*32+64

1+8+28+51+49+23+4 (16x) 1+8+28+52+50+22+3 (32x) 1+8+28+53+52+21+1 (32x) 1+8+28+53+53+21 (64x)

99 176 6 1+8+28+52+53+28+6  63360 tra  2^{3} × Δ_{5.1}
100 192 7 1+8+28+53+57+34+10+1  23040 tra  2^{3} × Δ_{5.2}
101 192 7 1+8+28+53+57+34+10+1 (64x)  2048 64+128  2^{2} × Δ_{6.10}

1+8+28+54+59+34+8 (128x)

102 196 6 1+8+28+54+60+36+9  225792 tra  Δ_{4.1} × Δ_{4.1}
103 224 7 1+8+28+55+65+46+18+3  129024 tra  2^{4} × Δ_{4.1}
104 256 8 1+8+28+56+70+56+28+8+1  10321920 tra  2^{8}

3.1 Universal covers

Of the graphs given here only Δ_{8.34}, Δ_{8.38}, Δ_{8.71}, Δ_{8.74}, Δ_{8.75} are not their own universal (0, 2)-cover. (The universal (0, 2)-cover of the first two is 2^{3} × Δ_{5.2}, that of the last three is 2^{8}.)

3.2 Spectra

There are two pairs and one triple of cospectral graphs here, namely Δ_{8.37}, Δ_{8.38} and Δ_{8.40}, Δ_{8.41} and Δ_{8.72}, Δ_{8.73}, Δ_{8.74}.

Seven graphs have integral spectrum, namely Δ_{8.13} (spectrum ±8^{1} ±4^{10} ±2^{24} 0^{10}), Δ_{8.71} (spectrum ±8^{1} ±4^{28} 0^{70}), Δ_{8.72}, Δ_{8.73}, Δ_{8.74} (spectrum ±8^{1} ±6^{2} ±4^{16} ±2^{30} 0^{30}), Δ_{8.75} (spectrum ±8^{1} ±6^{1} ±4^{22} ±2^{15} 0^{50}), and Δ_{8.104} (spectrum ±8^{1} ±6^{8} ±4^{28} ±2^{56} 0^{70}).

Among the bipartite (0, 2)-graphs of valency 8, one has 2\sqrt{2} ≤ λ_{2} ≤ 6, where the smallest value is attained only for Δ_{8.2}, and quite a few graphs have λ_{2} = 6.

4 Nonbipartite (0, 2)-graphs with k = 8

The nonbipartite (0, 2)-graphs with k = 8 have bipartite doubles found above. The number N(k) of nonisomorphic non-bipartite (0, 2)-graphs with k ≤ 8 is given in the following table.

\begin{matrix}k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ N(k) & 0 & 0 & 0 & 1 & 1 & 4 & 11 & 56 & 198 \end{matrix}

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

In one case we give spectral information in order to distinguish two graphs with otherwise identical data; λ_{i} denotes the i-th largest eigenvalue. We sometimes note in the tables that graphs are cospectral (abbreviated ‘cosp’); such information is given only when there was no other remark in the ‘graph’ column. See also §4.2. Many of these graphs can be found by adding a matching to a (0, 2)-graph of smaller valency. See §5.1.

# bipd k  v d distribution  locally  gsz orbits  graph
1  8.3 8 34 3 1+8+21+4 (10x)  C71  2 17*2
1+8+22+3 (14x)  C611
1+8+23+2 (10x)  C5111
2 8.3 8 34 3 1+8+20+5 (2x) C8 2 17*2
1+8+21+4 (8x)  C71
1+8+22+3 (12x)  C611
1+8+23+2 (12x)  C5111
3 8.4 8 34 3 1+8+20+5 (2x) C53 10 2*2+3*10
1+8+22+3 (20x)  C611
1+8+23+2 (10x)  C5111
1+8+25 (2x)  C311111
4  8.7 8 36 3 1+8+22+5  C3311  72 tra
5  8.7 8 36 3 1+8+22+5 (12x)  C611  12 12+12+12
1+8+23+4 (24x)  C5111
6 8.7 8 36 3 1+8+20+7 (12x) C8 12 4*6+12
1+8+22+5 (12x)  C611
1+8+23+4 (12x)  C5111
7 8.8 8 37 3 1+8+20+8 (6x) C8 12 2*1+2+3+3*6+12
1+8+22+6 (16x)  C611
1+8+23+5 (12x)  C5111
1+8+28 (3x)  C11111111
8 8.8 8 37 3 1+8+22+6 (28x) C3311 336 1+8+28
1+8+28 (9x)  C11111111
9 8.13 8 40 3 1+8+28+3  recta  1920 tra  cf. §5.2, 5.6
10 8.13 8 40 3 1+8+22+9 (32x)  C3311  384 8+32  cosp Γ_{8.16}
1+8+28+3 (8x)  C11111111
11 8.11 8 40 3 1+8+22+9 (20x) C3311 10 4*10
1+8+25+6 (20x)  C311111
12 8.12 8 40 3 1+8+20+11 (16x) C8 32 8+16+16
1+8+21+10 (16x)  C71
1+8+22+9 (8x)  C611
13 8.12 8 40 3 1+8+22+9 (24x) C3311 96 16+24
1+8+25+6 (16x)  C311111
14 8.15 8 40 3 1+8+25+6 (32x) C311111 192 8+32
1+8+28+3 (8x)  C11111111
15 8.13 8 40 4 1+8+20+10+1 (24x) C8  192 16+24
1+8+22+9 (16x)  C611
16 8.13 8 40 4 1+8+20+10+1 (8x) C8 32 3*8+16 cosp Γ_{8.10}
1+8+22+9 (8x)  C611
1+8+23+8 (16x)  C5111
1+8+28+3 (8x)  C11111111
17 8.15 8 40 4 1+8+20+10+1 (8x) C8 64 8+32
1+8+21+10 (32x)  C71
18 8.24 8 42 3 1+8+25+8 (32x) C311111 8 2+6*4+2*8
1+8+28+5 (10x)  C11111111
19 8.25 8 42 3 1+8+21+12 (16x) C71 8 3*2+3*4+3*8
1+8+22+11 (4x)  C611
1+8+23+10 (16x)  C5111
1+8+28+5 (6x)  C11111111
20 8.25 8 42 3 1+8+22+11 (4x) C3311 8 3*2+3*4+3*8
1+8+25+8 (24x)  C311111
1+8+28+5 (14x)  C11111111

# bipd k  v d distribution  locally  gsz orbits  graph
21 8.29 8 42 3 1+8+21+12 (24x)  C71  48 6+12+24  cosp Γ_{8.31}
1+8+22+11 (12x)  C611
1+8+28+5 (6x)  C11111111
22 8.29 8 42 3 1+8+22+11 (4x) C3311 16 2+2*4+2*8+16
1+8+25+8 (24x)  C311111
1+8+28+5 (14x)  C11111111
23 8.24 8 42 4 1+8+20+12+1 (2x) C8 8 2+6*4+2*8
1+8+21+11+1 (8x)  C71
1+8+21+12 (12x)  C71
1+8+22+11 (8x)  C611
1+8+23+10 (12x)  C5111
24 8.25 8 42 4 1+8+20+12+1 (2x) C8 8 3*2+3*4+3*8
1+8+22+10+1 (12x) C611
1+8+21+12 (4x)  C71
1+8+22+11 (4x)  C611
1+8+23+10 (20x)  C5111
25 8.25 8 42 4 1+8+20+12+1 (2x) C8 8 3*2+3*4+3*8
1+8+22+10+1 (4x)  C611
1+8+21+12 (8x)  C71
1+8+22+11 (2x)  C611
1+8+22+11 (2x)  C3311
1+8+23+10 (12x)  C5111
1+8+25+8 (12x)  C311111
26 8.26 8 42 4 1+8+20+12+1 (2x) C8 8 3*2+3*4+3*8 cosp Γ_{8.28}
1+8+20+12+1 (4x)  C53
1+8+22+10+1 (4x)  C611
1+8+21+12 (8x)  C71
1+8+22+11 (2x)  C611
1+8+22+11 (2x)  C3311
1+8+23+10 (8x)  C5111
1+8+25+8 (8x)  C311111
1+8+28+5 (4x)  C11111111
27 8.26 8 42 4 1+8+20+12+1 (2x) C8 32 2+8+2*16
1+8+22+10+1 (16x) C611
1+8+22+11 (8x)  C611
1+8+23+10 (16x)  C5111
28 8.26 8 42 4 1+8+20+12+1 (4x) C8 8 3*2+3*4+3*8 cosp Γ_{8.26}
1+8+22+10+1 (4x)  C611
1+8+21+12 (8x)  C71
1+8+22+11 (4x)  C611
1+8+23+10 (16x)  C5111
1+8+28+5 (6x)  C11111111
29 8.26 8 42 4 1+8+22+10+1 (8x) C3311 32 2+8+2*16
1+8+25+8 (16x)  C311111
1+8+28+5 (18x)  C11111111
30 8.29 8 42 4 1+8+20+12+1 (14x) C8  16 2+2*4+2*8+16
1+8+22+10+1 (4x)  C611
1+8+21+12 (16x)  C71
1+8+23+10 (8x)  C5111
31 8.29 8 42 4 1+8+20+12+1 (6x) C8 48 6+12+24 cosp Γ_{8.21}
1+8+22+10+1 (12x) C611
1+8+23+10 (24x)  C5111
32 8.31 8 44 3 1+8+22+13 (6x) C611 4 6*2+8*4
1+8+22+13 (2x)  C3311
1+8+23+12 (12x)  C5111
1+8+25+10 (20x)  C311111
1+8+28+7 (4x)  C11111111
33 8.32 8 44 3 1+8+22+13 (6x)  C611  4 6*2+8*4

# bipd k  v d distribution  locally  gsz orbits  graph
1+8+22+13 (2x)  C3311
1+8+23+12 (12x)  C5111
1+8+25+10 (20x)  C311111
1+8+28+7 (4x)  C11111111
34 8.33 8 48 3 1+8+23+16 (24x) C5111 48 24+24
1+8+25+14 (24x)  C311111
35 8.34 8 48 3 1+8+23+16  C5111  2880 tra  cf. §5.2
36 8.34 8 48 3 1+8+23+16 (24x)  C5111  480 24+24
1+8+28+11 (24x)  C11111111
37 8.34 8 48 3 1+8+28+11  recta  960 tra
38 8.37 8 48 3 1+8+23+16  C5111  192 tra  2 × Γ_{7.1}
39 8.37 8 48 3 1+8+23+16  C5111  192 tra  2 × Γ_{7.2}
40 8.37 8 48 3 1+8+25+14 (32x)  C311111  32 16+32  cosp Γ_{8.46}
1+8+28+11 (16x)  C11111111
41 8.37 8 48 3 1+8+25+14 (16x) C311111 64 16+32
1+8+28+11 (32x)  C11111111
42 8.37 8 48 3 1+8+25+14  C311111  192 tra  cosp Γ_{8.45}
43 8.38 8 48 3 1+8+23+16  C5111  960 tra  2 × Γ_{7.4}
44 8.38 8 48 3 1+8+23+16  C5111  960 tra  2 × Γ_{7.3}
45 8.38 8 48 3 1+8+25+14  C311111  96 tra  cosp Γ_{8.42}
46 8.38 8 48 3 1+8+25+14 (32x)  C311111  64 16+32  cosp Γ_{8.40}
1+8+28+11 (16x)  C11111111
47 8.38 8 48 3 1+8+28+11  recta  960 tra
48 8.39 8 48 3 1+8+25+14  C311111  32 16+32
49 8.39 8 48 3 1+8+25+14  C311111  96 tra
50 8.40 8 48 3 1+8+25+14 (32x)  C311111  16 2*4+8+2*16 cosp Γ_{8.53}
1+8+28+11 (16x)  C11111111
51 8.40 8 48 3 1+8+25+14  C311111  32 16+32
52 8.41 8 48 3 1+8+25+14 (16x)  C311111  16 2*4+8+2*16
1+8+28+11 (32x)  C11111111
53 8.41 8 48 3 1+8+25+14 (32x) C311111 32 16+32 cosp Γ_{8.50}
1+8+28+11 (16x)  C11111111
54 8.42 8 48 3 1+8+25+14  C311111  48 tra  λ_{2} = 4, λ_{3} = 3.909
55 8.42 8 48 3 1+8+25+14  C311111  48 tra  λ_{2} = 4, λ_{3} = 3.646
56 8.42 8 48 3 1+8+25+14  C311111  48 tra  cosp Γ_{8.54}
57 8.43 8 48 3 1+8+25+14  C311111  24 12+12+24
58 8.44 8 48 3 1+8+25+14  C311111  96 tra
59 8.45 8 48 3 1+8+25+14  C311111  48 tra
60 8.50 8 48 3 1+8+25+14 (24x)  C311111  48 24+24
1+8+28+11 (24x)  C11111111
61 8.52 8 48 3 1+8+25+14  C311111  96 tra
62 8.34 8 48 4 1+8+20+16+3  C53  2880 tra  K_{4} × Γ_{5.1}
63 8.34 8 48 4 1+8+22+15+2 (16x) C3311  64 16+16+16
1+8+25+14 (16x)  C311111
1+8+28+11 (16x)  C11111111
64 8.36 8 48 4 1+8+20+18+1 (2x) C53 4 6*2+9*4
1+8+21+17+1 (2x)  C71
1+8+22+16+1 (2x)  C3311
1+8+25+13+1 (2x)  C311111
1+8+23+16 (12x)  C5111
1+8+25+14 (24x)  C311111
1+8+28+11 (4x)  C11111111
65 8.36 8 48 4 1+8+21+17+1 (6x) C71 12 2*6+3*12
1+8+22+16+1 (12x) C611
1+8+23+15+1 (6x)  C5111
1+8+23+16 (24x)  C5111
66 8.37 8 48 4 1+8+25+12+2  C311111  384 tra  cosp Γ_{8.69}
67 8.37 8 48 4 1+8+25+12+2 (16x) C311111  128 16+32  cosp Γ_{8.70}

# bipd k  v d distribution  locally  gsz orbits  graph
1+8+25+14 (32x)  C311111
68 8.37 8 48 4 1+8+22+16+1  C3311  192 tra  2 × Γ_{7.5}
69 8.38 8 48 4 1+8+25+12+2  C311111  1920 tra  cosp Γ_{8.66}
70 8.38 8 48 4 1+8+25+12+2 (16x) C311111  128 16+32  cosp Γ_{8.67}
1+8+25+14 (32x)  C311111
71 8.38 8 48 4 1+8+22+16+1  C611  96 tra  2 × Γ_{7.6}
72 8.39 8 48 4 1+8+22+16+1 (24x) C611  24 4*12  2 × Γ_{7.11}
1+8+23+16 (24x)  C5111
73 8.40 8 48 4 1+8+21+16+2 (8x) C71 16 4*8+16 2 × Γ_{7.7}
1+8+22+16+1 (32x) C611
1+8+23+16 (8x)  C5111
74 8.41 8 48 4 1+8+21+16+2 (16x) C71 32 16+16+16 2 × Γ_{7.8}
1+8+22+16+1 (16x) C611
1+8+23+16 (16x)  C5111
75 8.42 8 48 4 1+8+21+16+2 (8x) C71 8 6*8 2 × Γ_{7.9}
1+8+22+16+1 (32x) C611
1+8+23+16 (8x)  C5111
76 8.43 8 48 4 1+8+21+16+2 (24x) C71 24 4*12 2 × Γ_{7.10}
1+8+22+16+1 (24x) C611
77 8.50 8 48 4 1+8+21+17+1 (8x) C71 16 4*8+16
1+8+22+16+1 (8x)  C611
1+8+23+15+1 (24x) C5111
1+8+23+16 (8x)  C5111
78 8.50 8 48 4 1+8+22+16+1 (24x) C611  24 12+12+24
1+8+23+16 (24x)  C5111
79 8.51 8 48 4 1+8+21+17+1 (6x) C71 12 2*6+3*12
1+8+23+15+1 (42x) C5111
80 8.51 8 48 4 1+8+21+17+1 (6x) C71 12 6*6+12
1+8+22+16+1 (12x) C611
1+8+23+15+1 (6x)  C5111
1+8+23+16 (24x)  C5111
81 8.52 8 48 4 1+8+21+16+2  C71  672 tra  2 × Γ_{7.12}
82 8.58 8 52 4 1+8+25+17+1 (8x)  C311111  8 3*4+5*8
1+8+25+18 (32x)  C311111
1+8+28+15 (12x)  C11111111
83 8.58 8 52 4 1+8+22+20+1 (4x) C3311 16 3*4+3*8+16
1+8+25+18 (32x)  C311111
1+8+28+15 (16x)  C11111111
84 8.58 8 52 4 1+8+22+19+2 (8x) C611 16 3*4+3*8+16
1+8+23+18+2 (16x) C5111
1+8+22+20+1 (12x) C611
1+8+23+20 (8x)  C5111
1+8+25+18 (8x)  C311111
85 8.59 8 52 4 1+8+25+15+3 (2x) C311111 12 2*2+8*6
1+8+22+20+1 (12x) C611
1+8+23+19+1 (12x) C5111
1+8+28+14+1 (6x)  C11111111
1+8+25+18 (6x)  C311111
1+8+28+15 (14x)  C11111111
86 8.59 8 52 4 1+8+22+20+1 (4x) C3311 8 5*4+4*8
1+8+28+14+1 (4x)  C11111111
1+8+25+18 (32x)  C311111
1+8+28+15 (12x)  C11111111
87 8.60 8 52 4 1+8+23+18+2 (24x) C5111  48 2+6+8+12+24
1+8+22+20+1 (12x) C611
1+8+22+21 (8x)  C611
1+8+25+18 (8x)  C311111
88 8.60 8 52 4 1+8+22+20+1 (4x)  C3311  16 2*2+2*4+3*8+16

# bipd k  v d distribution  locally  gsz orbits  graph
1+8+25+18 (32x)  C311111
1+8+28+15 (16x)  C11111111
89 8.61 8 52 4 1+8+20+21+2 (6x) C8 48 2+3*6+8+24
1+8+23+18+2 (24x) C5111
1+8+28+14+1 (6x)  C11111111
1+8+25+18 (8x)  C311111
1+8+28+15 (8x)  C11111111
90 8.63 8 56 4 1+8+25+18+4 (4x) C311111 8 4*4+5*8
1+8+25+20+2 (32x) C311111
1+8+28+17+2 (8x)  C11111111
1+8+25+22 (4x)  C311111
1+8+28+19 (8x)  C11111111
91 8.63 8 56 4 1+8+25+18+4 (4x) C311111 8 4*4+5*8
1+8+25+20+2 (8x)  C311111
1+8+25+22 (12x)  C311111
1+8+28+19 (32x)  C11111111
92 8.66 8 56 4 1+8+25+20+2 (16x) C311111  16 3*8+2*16
1+8+25+22 (8x)  C311111
1+8+28+19 (32x)  C11111111
93 8.66 8 56 4 1+8+25+20+2 (16x) C311111  8 7*8
1+8+25+22 (8x)  C311111
1+8+28+19 (32x)  C11111111
94 8.67 8 56 4 1+8+25+18+4 (4x) C311111 16 2*4+2*8+2*16
1+8+25+20+2 (32x) C311111
1+8+28+17+2 (16x) C11111111
1+8+25+22 (4x)  C311111
95 8.68 8 56 4 1+8+25+18+4 (4x) C311111 16 2*4+2*8+2*16
1+8+25+20+2 (16x) C311111
1+8+25+22 (4x)  C311111
1+8+28+19 (32x)  C11111111
96 8.69 8 56 4 1+8+25+20+2 (16x) C311111  4 14*4
1+8+28+17+2 (8x)  C11111111
1+8+25+22 (8x)  C311111
1+8+28+19 (24x)  C11111111
97 8.71 8 64 3 1+8+25+30  C311111  46080 tra  K_{4} × Γ_{5.2}
98 8.71 8 64 3 1+8+25+30  C311111  4608 tra  cf. §5.3
99 8.72 8 64 3 1+8+25+30 (48x)  C311111  256 16+16+32
1+8+28+27 (16x)  C11111111
100 8.72 8 64 3 1+8+25+30 (16x) C311111 128 16+16+32 cosp Γ_{8.101}
1+8+28+27 (48x)  C11111111
101 8.72 8 64 3 1+8+25+30 (16x) C311111 256 16+16+32 cosp Γ_{8.100}
1+8+28+27 (48x)  C11111111
102 8.73 8 64 3 1+8+25+30 (32x) C311111 128 32+32 cosp Γ_{8.103}
1+8+28+27 (32x)  C11111111
103 8.73 8 64 3 1+8+25+30 (32x) C311111 64 4*16 cosp Γ_{8.102}
1+8+28+27 (32x)  C11111111
104 8.74 8 64 3 1+8+25+30 (32x) C311111 512 32+32 cosp Γ_{8.102}
1+8+28+27 (32x)  C11111111
105 8.74 8 64 3 1+8+25+30  C311111  15360 tra  2^{8}/⟨1^{3}0^{5}, 01^{6}⟩
106 8.74 8 64 3 1+8+25+30 (32x)  C311111  768 32+32  cosp Γ_{8.102}
1+8+28+27 (32x)  C11111111
107 8.74 8 64 3 1+8+28+27  recta  1536 tra  cosp Γ_{8.108}
108 8.74 8 64 3 1+8+28+27  recta  9216 tra  2^{8}/⟨1^{5}0^{3}, 0^{2}1^{6}⟩
109 8.75 8 64 3 1+8+25+30  C311111  7680 32+32
110 8.75 8 64 3 1+8+25+30 (48x)  C311111  384 4*16
1+8+28+27 (16x)  C11111111
111 8.75 8 64 3 1+8+25+30 (32x) C311111 2304 32+32
1+8+28+27 (32x)  C11111111

# bipd k  v d distribution  locally  gsz orbits  graph
112 8.77 8 64 3 1+8+28+27  recta  1152 tra
113 8.72 8 64 4 1+8+25+24+6  C311111  1024 tra  2 × Γ_{7.18}
114 8.72 8 64 4 1+8+25+24+6  C311111  512 tra  2 × Γ_{7.19}
115 8.73 8 64 4 1+8+25+24+6  C311111  1536 tra  2 × Γ_{7.21}
116 8.73 8 64 4 1+8+25+24+6  C311111  192 tra  2 × Γ_{7.20}
117 8.74 8 64 4 1+8+22+24+9  C611  1536 tra  2^{2} × Γ_{6.2}
118 8.74 8 64 4 1+8+22+24+9  C3311  9216 tra  2^{2} × K_{4} × K_{4}
119 8.74 8 64 4 1+8+22+24+9 (32x) C611  768 32+32  cosp Γ_{8.113−116,119−122}
1+8+28+27 (32x)  C11111111
120 8.74 8 64 4 1+8+22+24+9 (32x) C3311 4608 32+32 cosp Γ_{8.113−116,119−122}
1+8+28+27 (32x)  C11111111
121 8.74 8 64 4 1+8+25+24+6  C311111  3072 tra  2 × Γ_{7.25}
122 8.74 8 64 4 1+8+25+24+6  C311111  512 tra  2 × Γ_{7.26}
123 8.75 8 64 4 1+8+22+24+9 (32x) C3311  2304 32+32  K_{4} × Γ_{5.4}
1+8+25+30 (32x)  C311111
124 8.76 8 64 4 1+8+22+24+9 (16x) C611 16 4*16 2 × Γ_{7.16}
1+8+23+24+8 (48x) C5111
125 8.76 8 64 4 1+8+25+26+4 (16x) C311111  16 4*16
1+8+25+28+2 (16x) C311111
1+8+28+25+2 (32x) C11111111
126 8.76 8 64 4 1+8+25+24+6 C311111 48 16+48 2 × Γ_{7.17}
127 8.76 8 64 4 1+8+25+26+4 (32x) C311111  16 4*16
1+8+28+25+2 (32x) C11111111
128 8.76 8 64 4 1+8+28+25+2 (48x) recta  48 16+48

1+8+28+27 (16x)

129 8.77 8 64 4 1+8+22+24+9 (16x) C611 96 16+48 2 × Γ_{7.24}
1+8+23+24+8 (48x) C5111
130 8.77 8 64 4 1+8+25+26+4 (32x) C311111  64 32+32
1+8+28+25+2 (32x) C11111111
131 8.77 8 64 4 1+8+28+25+2 (48x) recta  96 16+48

1+8+28+27 (16x)

132 8.78 8 64 4 1+8+25+26+4 (16x) C311111  8 8*8
1+8+25+28+2 (8x)  C311111
1+8+28+25+2 (24x) C11111111
1+8+25+30 (8x)  C311111
1+8+28+27 (8x)  C11111111
133 8.79 8 64 4 1+8+21+24+10 (4x) C71  8 8*4+4*8 2 × Γ_{7.14}
1+8+22+24+9 (4x)  C611
1+8+22+24+9 (4x)  C3311
1+8+23+24+8 (28x) C5111
1+8+25+24+6 (16x) C311111
1+8+28+24+3 (8x)  C11111111
134 8.79 8 64 4 1+8+25+24+6 (4x) C311111 8 8*4+4*8
1+8+25+25+5 (4x)  C311111
1+8+25+26+4 (16x) C311111
1+8+25+27+3 (8x)  C311111
1+8+28+24+3 (4x)  C11111111
1+8+28+25+2 (16x) C11111111
1+8+28+27 (12x)  C11111111
135 8.80 8 64 4 1+8+25+23+7 (4x) C311111 8 8*4+4*8
1+8+25+25+5 (8x)  C311111
1+8+25+26+4 (4x)  C311111
1+8+25+27+3 (8x)  C311111
1+8+25+28+2 (8x)  C311111
1+8+28+25+2 (12x) C11111111
1+8+28+27 (20x)  C11111111
136 8.81 8 64 4 1+8+25+26+4 (24x) C311111  4 16*4
1+8+25+28+2 (8x)  C311111

# bipd k  v d distribution  locally  gsz orbits  graph
1+8+28+25+2 (24x)  C11111111
1+8+28+27 (8x)  C11111111
137 8.81 8 64 4 1+8+22+24+9 (12x) C611 12 4+5*12 2 × Γ_{7.13}
1+8+23+24+8 (24x)  C5111
1+8+25+24+6 (24x)  C311111
1+8+28+24+3 (4x)  C11111111
138 8.82 8 64 4 1+8+21+24+10 (2x) C71 4 8*2+12*4 2 × Γ_{7.15}
1+8+22+24+9 (8x)  C611
1+8+22+24+9 (2x)  C3311
1+8+23+24+8 (26x)  C5111
1+8+25+24+6 (20x)  C311111
1+8+28+24+3 (6x)  C11111111
139 8.83 8 64 4 1+8+25+26+4 (16x) C311111 16 2*8+3*16
1+8+28+24+3 (8x)  C11111111
1+8+25+28+2 (16x)  C311111
1+8+28+25+2 (24x)  C11111111
140 8.83 8 64 4 1+8+28+24+3 (8x) recta 112 8+56

1+8+28+25+2 (56x)

141 8.83 8 64 4 1+8+22+24+9 (56x) C611 336 8+56 2 × Γ_{7.23}
1+8+28+24+3 (8x)  C11111111
142 8.83 8 64 4 1+8+22+24+9 (8x) C3311 48 8+8+48 2 × Γ_{7.22}
1+8+25+24+6 (48x)  C311111
1+8+28+24+3 (8x)  C11111111
143 8.80 8 64 5 1+8+21+23+10+1 (12x) C71 24 4+5*12 2 × Γ_{7.29}
1+8+23+23+8+1 (12x)  C5111
1+8+23+24+8 (24x)  C5111
1+8+25+24+6 (16x)  C311111
144 8.83 8 64 5 1+8+21+23+10+1 (8x) C71 112 8+56 2 × Γ_{7.30}
1+8+23+24+8 (56x)  C5111
145 8.91 8 72 4 1+8+25+28+10 (40x) C311111 16 3*8+3*16 2 × Γ_{7.32}
1+8+28+28+7 (32x)  C11111111
146 8.91 8 72 4 1+8+25+32+6 (24x) C311111 32 2*4+4*8+2*16 cosp Γ_{8.147}
1+8+28+29+6 (8x)  C11111111
1+8+28+32+3 (32x)  C11111111
1+8+28+35 (8x)  C11111111
147 8.91 8 72 4 1+8+25+32+6 (24x) C311111 32 3*8+3*16 cosp Γ_{8.146}
1+8+28+32+3 (48x)  C11111111
148 8.91 8 72 4 1+8+25+32+6 (24x) C311111 192 24+48
1+8+28+29+6 (48x)  C11111111
149 8.91 8 72 4 1+8+25+32+6 (24x) C311111 192 24+48
1+8+28+35 (48x)  C11111111
150 8.92 8 72 4 1+8+25+28+10 (40x) C311111 64 8+2*16+32 2 × Γ_{7.31}
1+8+28+28+7 (32x)  C11111111
151 8.92 8 72 4 1+8+25+32+6 (24x) C311111 32 5*8+2*16 cosp Γ_{8.152}
1+8+28+29+6 (8x)  C11111111
1+8+28+32+3 (32x)  C11111111
1+8+28+35 (8x)  C11111111
152 8.92 8 72 4 1+8+25+32+6 (24x) C311111 96 24+24+24 cosp Γ_{8.151}
1+8+28+29+6 (24x)  C11111111
1+8+28+35 (24x)  C11111111
153 8.93 8 72 4 1+8+25+32+6 (24x) C311111 160 4+8+20+40
1+8+28+32+3 (48x)  C11111111
154 8.95 8 80 4 1+8+25+34+12 (32x) C311111 32 6*8+2*16 cosp Γ_{8.156}
1+8+28+31+12 (8x)  C11111111
1+8+28+34+9 (8x)  C11111111
1+8+28+37+6 (8x)  C11111111
1+8+28+40+3 (24x)  C11111111
155 8.95 8 80 4 1+8+28+31+12 (16x)  recta  192 16+16+48

# bipd k  v d distribution  locally  gsz orbits  graph

1+8+28+34+9 (48x) 1+8+28+40+3 (16x)

156 8.95 8 80 4 1+8+25+34+12 (32x) C311111 64 3*16+32 cosp Γ_{8.154}
1+8+28+37+6 (48x)  C11111111
157 8.96 8 80 4 1+8+25+34+12 (32x) C311111 32 5*16
1+8+28+31+12 (16x)  C11111111
1+8+28+34+9 (16x)  C11111111
1+8+28+37+6 (16x)  C11111111
158  8.96 8 80 4 1+8+28+40+3  recta  480 tra
159  8.97 8 80 4 1+8+25+33+13 (16x)  C311111  16 4*8+3*16
1+8+28+32+11 (8x)  C11111111
1+8+25+36+10 (16x)  C311111
1+8+28+36+7 (24x)  C11111111
1+8+28+39+4 (16x)  C11111111
160 8.97 8 80 4 1+8+25+33+13 (16x) C311111 16 4*8+3*16
1+8+25+34+12 (16x)  C311111
1+8+28+32+11 (8x)  C11111111
1+8+28+33+10 (16x)  C11111111
1+8+28+36+7 (24x)  C11111111
161 8.95 8 80 5 1+8+22+28+17+4 (16x) C611 192 16+16+48 2^{2} × Γ_{6.4}
1+8+23+29+16+3 (48x) C5111
1+8+25+31+14+1 (16x) C311111
162 8.95 8 80 5 1+8+22+28+17+4 (8x) C611 96 4*8+2*24
1+8+23+29+16+3 (24x) C5111
1+8+25+31+14+1 (8x)  C311111
1+8+28+31+12 (8x)  C11111111
1+8+28+34+9 (24x)  C11111111
1+8+28+40+3 (8x)  C11111111
163 8.95 8 80 5 1+8+25+30+14+2 (16x) C311111 32 3*16+32 2 × Γ_{7.34}
1+8+25+32+14 (32x)  C311111
1+8+28+32+11 (32x)  C11111111
164 8.96 8 80 5 1+8+25+30+14+2 (16x) C311111 16 5*16 2 × Γ_{7.35}
1+8+25+32+14 (32x)  C311111
1+8+28+32+11 (32x)  C11111111
165  8.96 8 80 5 1+8+25+31+14+1  C311111  480 tra  2^{2} × Γ_{6.3}
166  8.96 8 80 5 1+8+25+31+14+1 (40x) C311111  240 40+40
1+8+28+40+3 (40x)  C11111111
167 8.99 8 88 4 1+8+25+36+18 (40x) C311111 160 8+40+40 2 × Γ_{7.37}
1+8+28+36+15 (48x)  C11111111
168  8.99 8 88 4 1+8+25+36+18  C311111  31680 tra  K_{4} × Δ_{5.1}
169  8.99 8 88 4 1+8+25+36+18 (24x)  C311111  576 16+24+48
1+8+28+42+9 (64x)  C11111111
170 8.100 8 96 4 1+8+28+43+16 (64x) recta 768 32+64

1+8+28+53+6 (32x)

171 8.100 8 96 4 1+8+28+53+6  recta  11520 tra  cf. §5.2
172 8.100 8 96 5 1+8+25+35+22+5 (64x) C311111  256 32+64  2^{2} × Γ_{6.5}
1+8+28+38+19+2 (32x) C11111111
173 8.100 8 96 5 1+8+25+35+22+5 (32x) C311111  128 2*16+2*32
1+8+28+38+19+2 (16x) C11111111
1+8+28+43+16 (32x)  C11111111
1+8+28+53+6 (16x)  C11111111
174 8.100 8 96 5 1+8+25+37+22+3 (48x) C311111 192 48+48 2 × Γ_{7.42}
1+8+28+40+19 (48x)  C11111111
175 8.100 8 96 5 1+8+25+37+22+3 (32x) C311111  128 32+32+32 2 × Γ_{7.43}
1+8+28+37+19+3 (32x) C11111111
1+8+28+40+19 (32x)  C11111111
176 8.100 8 96 5 1+8+25+37+22+3 C311111 11520 tra K_{4} × Δ_{5.2}
177 8.100 8 96 5 1+8+25+37+22+3 (32x) C311111  768 32+64

# bipd k  v d distribution  locally  gsz orbits  graph
1+8+28+43+16 (64x)  C11111111
178 8.100 8  96 5 1+8+28+38+19+2  recta  3840 tra  2^{2} × Γ_{6.6}
179 8.100 8  96 5 1+8+28+38+19+2 (48x)  recta  1920 48+48

1+8+28+53+6 (48x)

180 8.100 8  96 5 1+8+28+37+19+3  recta  1920 tra  2 × Γ_{7.44}
181 8.101 8  96 5 1+8+25+37+22+3 (16x)  C311111  128 2*8+16+2*32
1+8+25+38+24 (32x)  C311111
1+8+28+40+19 (16x)  C11111111
1+8+28+41+18 (32x)  C11111111
182 8.101 8 96 5 1+8+25+37+22+3 (16x) C311111 64 4*8+2*16+32
1+8+25+38+24 (16x)  C311111
1+8+28+40+19 (8x)  C11111111
1+8+28+41+18 (16x)  C11111111
1+8+28+44+15 (32x)  C11111111
1+8+28+53+6 (8x)  C11111111
183 8.101 8 96 5 1+8+25+38+22+2 (32x) C311111 64 32+32+32 2 × Γ_{7.38}
1+8+28+38+19+2 (32x)  C11111111
1+8+28+40+19 (32x)  C11111111
184 8.101 8 96 5 1+8+25+35+22+5 (16x) C311111 64 4*16+32 2 × Γ_{7.39}
1+8+25+36+22+4 (16x)  C311111
1+8+28+37+19+3 (16x)  C11111111
1+8+28+38+19+2 (48x)  C11111111
185 8.101 8 96 5 1+8+25+35+22+5 (32x) C311111 256 32+64 2 × Γ_{7.40}
1+8+28+38+19+2 (64x)  C11111111
186 8.100 8  96 6 1+8+23+32+23+8+1  C5111  5760 tra  2^{3} × Γ_{5.1}
187 8.100 8  96 6 1+8+23+32+23+8+1 (48x)  C5111  960 48+48  2 × Γ_{7.47}
1+8+28+37+19+3 (48x)  C11111111
188 8.103 8 112 4 1+8+28+45+30 (64x) recta 2304 16+48+48

1+8+28+55+20 (48x)

189 8.103 8 112 5 1+8+25+39+30+9 (64x) C311111 384 16+48+48 2^{2} × Γ_{6.8}
1+8+28+42+27+6 (48x)  C11111111
190 8.103 8 112 5 1+8+25+39+30+9 (32x) C311111 192 2*8+4*24
1+8+28+42+27+6 (24x)  C11111111
1+8+28+45+30 (32x)  C11111111
1+8+28+55+20 (24x)  C11111111
191 8.103 8 112 5 1+8+25+39+30+9  C311111  16128 tra  2 × K_{4} × Δ_{4.1}
192 8.103 8 112 5 1+8+25+39+30+9 (48x)  C311111  768 16+32+64  2 × Γ_{7.50}
1+8+28+45+27+3 (64x)  C11111111
193 8.104 8 128 4 1+8+28+56+35  recta  645120 tra  2 × Γ_{7.51}
194 8.104 8 128 5 1+8+28+46+35+10  recta  92160 tra  2^{3} × Γ_{5.2}
195 8.104 8 128 5 1+8+28+46+35+10 (64x)  recta  15360 64+64  2 × Γ_{7.53}

1+8+28+56+35 (64x)

196 8.104 8 128 6 1+8+25+40+35+16+3  C311111  92160 tra  2^{5} × K_{4}
197 8.104 8 128 6 1+8+25+40+35+16+3 (64x) C311111  4608 64+64  2^{3} × Γ_{5.4}
1+8+28+46+35+10 (64x)  C11111111
198 8.104 8 128 6 1+8+25+40+35+16+3 (32x) C311111 1536 32+32+64 2 × Γ_{7.56}
1+8+28+46+35+10 (64x)  C11111111
1+8+28+56+35 (32x)  C11111111

4.1 Recognition

All graphs are uniquely determined by the combinatorial data given above, with the exception of the three graphs Γ_{8.54}, Γ_{8.55}, Γ_{8.56}. The spectrum distinguishes Γ_{8.55} from the other two, but Γ_{8.54} and Γ_{8.56} are also cospectral. They can be distinguished as follows: Fix a vertex ∞. Vertices at distance two can be identified with pairs of vertices in Ω := Γ(∞), that is, with edges in the complete graph on Ω. Vertices at distance three from ∞ then give rise to a graph on Ω that is regular of valency 2. We can list the frequencies with which the various possibilities (C_{8}, C_{7}, C_{6}, C_{4}, C_{3}, 2C_{4}, C_{4} + C_{3}, 2C_{3}) occur. Each of these three graphs has a transitive group, so the choice of ∞ does not matter. For Γ_{8.54}: 3*C_{7}, 3*C_{6}, 2*C_{5}, 2*C_{3}, 1*(C_{4} + C_{3}), 3*(2C_{3}). For Γ_{8.55}: 2*C_{7}, 1*C_{6}, 2*C_{5}, 2*C_{3}, 2*(C_{4} + C_{3}), 5*(2C_{3}). For Γ_{8.56}: 1*C_{7}, 2*C_{6}, 1*C_{5}, 2*C_{3}, 2*(C_{4} + C_{3}), 6*(2C_{3}).

4.2 Spectra

Among the nonbipartite (0, 2)-graphs of valency 8, one has 2 ≤ λ_{2} ≤ 6, where the smallest value is attained only for Γ_{8.9}, and quite a few graphs have λ_{2} = 6.

Graphs with integral spectrum (listed are the multiplicities for the eigenvalues 8, 6, ..., −6):

v  graph  8 6  4  2  0 −2 −4 −6
40  Γ_{8.9}  1 0  0 20  5  4 10  0
40  Γ_{8.i}, i = 10, 16  1 0  4 12  5 12  6  0
40  Γ_{8.15}  1 0  6  8  5 16  4  0
64  Γ_{8.i}, i = 97, 98  1 0 13  0 35  0 15  0
64  Γ_{8.99}  1 0 10 12 15 18  6  2
64  Γ_{8.i}, i = 100, 101  1 0  8 16 15 14  8  2
64  Γ_{8.i}, i = 102, 103, 104, 106  1 0  9 14 15 16  7  2
64  Γ_{8.105}  1 0 11 10 15 20  5  2
64  Γ_{8.i}, i = 107, 108  1 0  7 18 15 12  9  2
64  Γ_{8.109}  1 0 12  5 25 10 10  1
64  Γ_{8.110}  1 0 11  7 25  8 11  1
64  Γ_{8.111}  1 0 10  9 25  6 12  1
64 Γ_{8.i}, i = 113, 114, 115, 116, 119, 120, 121, 122 1 1  7 15 15 15  9  1
64  Γ_{8.i}, i = 117, 118  1 2  7 12 15 18  9  0
64  Γ_{8.123}  1 1 10  6 25  9 12  0
128  Γ_{8.193}  1 1 21 21 35 35  7  7
128  Γ_{8.194}  1 3 13 31 35 25 15  5
128  Γ_{8.195}  1 2 17 26 35 30 11  6
128  Γ_{8.196}  1 5 13 25 35 31 15  3
128  Γ_{8.197}  1 4 13 28 35 28 15  4
128  Γ_{8.198}  1 3 15 27 35 29 13  5

(Note that all integral eigenvalues of a (0, 2)-graph have the same parity as the valency k, since the adjacency matrix A satisfies A^{2} = kI + 2B for some integral matrix B.)

Apart from the cases already noted in the table, and those apparent from this eigenvalue table, there are two cospectral pairs and one cospectral quadruple: Γ_{8.68}, Γ_{8.71} and Γ_{8.73}, Γ_{8.74} and Γ_{8.38}, Γ_{8.39}, Γ_{8.43}, Γ_{8.44}.

5 Some constructions

5.1 Adding a matching

Let Γ be a (0, 2)-graph of valency k, and let σ be an automorphism of order 2 such that x and σ(x) have distance different from 0, 1 or 3 for all vertices x. Add edges (i, σ(i)) to Γ to obtain a graph Δ of valency k + 1 on the same number of vertices. If Γ is bipartite, or, more generally, if whenever a and b are two distinct vertices with two common neighbours, σ(a) is nonadjacent to b, then Δ is a (0, 2)-graph again.

On can go in the opposite direction: given a (0, 2)-graph of valency k + 1 and an automorphism σ of which all orbits are edges. Removing these edges yields a graph of which all connected components are (0, 2)-graphs of valency k.

In the situation discussed here, the eigenvalues of Δ are those of Γ shifted by ±1. Indeed, for each eigenvalue θ of Γ, the θ-eigenspace has a basis of vectors u with σ(u) = ±u. (For arbitrary u, consider u ± σ(u).) Such a u is also eigenvector of Δ, with eigenvalue θ ± 1.

This construction allows one to go back and forth between Δ_{2.1} (the quadrangle) and Γ_{3.1} (K_{4}), and for example between Δ_{7.1} and Γ_{8.i}, i = 40, 41, 42, 66, 67. We give the correspondences in the table below.

Δ_{3.1}  Γ_{4.1}  Δ_{7.8}  Γ_{8.57}  Δ_{7.36}  Γ_{8.167−169}
Δ_{4.2}  Γ_{5.2−4}  Δ_{7.9}  Γ_{8.48−49}  Δ_{7.37}  Γ_{8.181−185}
Δ_{5.2}  Γ_{6.5−6}  Δ_{7.10}  Γ_{8.61}  Δ_{7.38}  Δ_{8.34,38}, Γ_{8.170−180}
Δ_{5.3}  Γ_{6.8}  Δ_{7.11}  Γ_{8.94}  Δ_{7.39}  Γ_{8.188−192}
Δ_{5.4} Δ_{6.3}, Γ_{6.9−11} Δ_{7.12}  Γ_{8.90−91}  Δ_{7.40}  Δ_{8.71,74−75}, Γ_{8.193−198}
Δ_{6.1}  Γ_{7.18−19}  Δ_{7.13}  Γ_{8.95}  Γ_{5.3}  Γ_{6.1}
Δ_{6.2}  Γ_{7.20−21}  Δ_{7.16}  Γ_{8.96}  Γ_{6.7}  Γ_{7.3}
Δ_{6.3}  Γ_{7.25−26}  Δ_{7.17}  Γ_{8.92−93}  Γ_{6.9}  Γ_{7.25}
Δ_{6.4}  Γ_{7.31}  Δ_{7.18}  Γ_{8.125,127−128}  Γ_{6.10}  Γ_{7.25,27}
Δ_{6.6}  Γ_{7.32}  Δ_{7.19}  Γ_{8.132}  Γ_{6.11}  Γ_{7.26}
Δ_{6.7}  Γ_{7.34}  Δ_{7.20} Γ_{8.99−101,113−114} Γ_{7.41}  Γ_{8.63,70}
Δ_{6.8}  Γ_{7.35}  Δ_{7.21} Γ_{8.102−103,115−116} Γ_{7.42}  Γ_{8.45}
Δ_{6.9}  Γ_{7.37}  Δ_{7.22}  Γ_{8.112,130−131}  Γ_{7.43}  Γ_{8.46,63}
Δ_{6.10}  Γ_{7.38−40}  Δ_{7.23} Γ_{8.104−108,121−122} Γ_{7.44}  Γ_{8.37,47}
Δ_{6.11} Δ_{7.2}, Γ_{7.41−45} Δ_{7.24}  Γ_{8.136}  Γ_{7.45}  Γ_{8.37,69}
Δ_{6.12}  Γ_{7.48−50}  Δ_{7.25}  Γ_{8.135}  Γ_{7.46}  Γ_{8.35,44,62}
Δ_{6.13} Δ_{7.23}, Γ_{7.51−56} Δ_{7.26}  Γ_{8.134}  Γ_{7.47}  Γ_{8.36}
Δ_{7.1} Γ_{8.40−42,66−67} Δ_{7.28}  Γ_{8.139−140}  Γ_{7.51}  Γ_{8.105}
Δ_{7.2} Γ_{8.45−47,69−70} Δ_{7.30}  Γ_{8.150−152}  Γ_{7.52}  Γ_{8.97,108,111,121}
Δ_{7.3}  Γ_{8.59}  Δ_{7.31}  Γ_{8.153}  Γ_{7.53}  Γ_{8.106,109}
Δ_{7.4}  Γ_{8.50−51}  Δ_{7.32}  Γ_{8.145−149}  Γ_{7.54}  Γ_{8.97,105,109,118,121,123}
Δ_{7.5}  Γ_{8.52−53}  Δ_{7.33}  Γ_{8.159−160}  Γ_{7.55} Γ_{8.98,106,110−111,120,122−123}
Δ_{7.6}  Γ_{8.54−56}  Δ_{7.34}  Γ_{8.154−156,163}  Γ_{7.56}  Γ_{8.104,110}
Δ_{7.7}  Γ_{8.58}  Δ_{7.35}  Γ_{8.157−158,164}

5.2 Antipodal quotients

If, for some graph Γ, being at maximal distance is an equivalence relation, we can define the quotient Γ/α of Γ under the map α sending each vertex to its equivalence class. For (0, 2)- graphs of valency 8, this produces a (0, 2)-graph again in four cases: the antipodal quotients of the four graphs Δ_{8.13}, Δ_{8.100}, Δ_{8.104} and Γ_{8.186} are the four graphs Γ_{8.9}, Γ_{8.171}, Δ_{8.71} and Γ_{8.35}, respectively.

5.3 Γ_{8.98} as quotient of a folded cube

The graph Γ_{8.98} is obtained from 2^{8}/1 by taking the quotient under x ↦ π(x) + u, where π is the coordinate permutation (12), and u = (00000111).

5.4 Δ_{8.19} as cover of a directed graph

Let Σ be a directed graph with vertex set X of size v. Construct an undirected cover Γ with vertex set Z_{4} × X of size 4v by letting (i, x) ∼ (i + 1, y) when (x, y) is an edge of Σ. Let T be the underlying undirected graph of Σ. If in T any two vertices are joined by zero or two paths of length 2 with both corresponding Σ-edges in the same direction, and by zero or two paths of length 2 with the corresponding Σ-edges in opposite directions, then each connected component of Γ will be a (0,2)-graph. If T is connected, then the graph Γ is connected when T is not bipartite, and has two connected components otherwise.

In particular, consider the graph Σ on the flags of the Fano plane, with a directed edge (p, L) → (q, M) whenever p ≠ q, L ≠ M and q ∈ L. (Now T is the distance-2 graph of the generalized hexagon GH(2, 1).) It satisfies the given conditions, and the graph Γ is a (0,2)-graph on 84 vertices. It is Δ_{8.19}. The group is 4.L_{3}(2).2, acting flag-transitively.

5.5 Δ_{8.62} as cover of the co-Heawood graph

Make the seven points of the Fano plane together with an additional element 0 into a binary vector space V of dimension 3, by agreeing that the sum of three distinct collinear points is 0. Similarly, let W be the binary vector space of dimension 3 spanned by the lines, where the sum of three concurrent lines is 0. Construct a bipartite graph with 56 vertices (p, w), where p is a point and w ∈ W, and 56 vertices (L, v), where L is a line and v ∈ V. Let (p, 0) ∼ (L, 0) when p ∉ L, and let (p, M) ∼ (L, q) when p ∉ L and p, q ∈ M and q ∈ L, M, and finally, whenever (p, w) ∼ (L, v), let also (p, w + L) ∼ (L, v) and (p, w) ∼ (L, v + p). The resulting graph is the (0,2)-graph Δ_{8.62}. It has automorphism group 2^{6}.L_{3}(2).2. Mapping (p, w) to p and (L, v) to L, we see that this graph is an 8-cover of the co-Heawood graph.

5.6 Γ_{8.9} from GQ(3, 3)

Up to duality there is a unique generalized quadrangle of order 3. It has 40 points and 40 lines. One construction is given by the isotropic points and totally isotropic lines in Sp(4, 3) (it has regular points, but lines are not regular). The dual quadrangle is obtained by taking the isotropic points and totally isotropic lines on O(5, 3). A third construction, isomorphic with the first, is found by taking the 40 nonisotropic points in U(4, 2), adjacent when orthogonal (so that lines are orthogonal bases, and lines joining nonadjacent points are tangents). Take the collinearity graph of this last generalized quadrangle, fix a totally isotropic line L, and remove the edges of the five K_{4,4} subgraphs in the five tangent planes x^{⊥} for x ∈ L. (In other words, remove an edge if the line carrying it meets the line L.) The result is the (0,2)-graph Γ_{8.9}. Its group is 2^{4}.Sym(5). Its bipartite double is Δ_{8.13}.

6 Acknowledgment

Each of Aart Blokhuis, Koen Thas and Henny Wilbrink contributed to the description of Γ_{8.9} given in §5.6.

References

[1] Andries E. Brouwer, Classification of small (0,2)-graphs, J. Combinatorial Th. (A) 113 (2006) 1636–1645.

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

[3] 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.

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

[5] P. Kaski and P. R. J. Östergård, Classification Algorithms for Codes and Designs, Springer, Berlin, 2006.

[6] D. E. Knuth, Dancing links, in Millennial Perspectives in Computer Science, J. Davies, B. Roscoe, and J. Woodcock (Eds.), Palgrave, Basingstoke, England, 2000, pp. 187–214.

[7] B. D. McKay, nauty user’s guide (version 1.5), Technical Report TR-CS-90-02, Computer Science Department, Australian National University, Canberra, 1990.

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

[9] 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.

[10] Martyn Mulder, (0, λ)-graphs and n-cubes, Discrete Math. 28 (1979) 179–188.

[11] 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.

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

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