\documentclass[a4paper]{article}
\usepackage{latexsym}
\usepackage{supertab}
\newcommand{\Zz}{{\bf Z}}

\oddsidemargin=0mm\evensidemargin=0mm\topmargin=0mm
\textwidth=14.5cm\textheight=22cm

\title{Classification of small (0,2)-graphs}
\author{Andries E. Brouwer\\
{\small Department of Mathematics, Technological University Eindhoven,}\\[-3pt]
{\small P.O. Box 513, 5600~MB Eindhoven, The Netherlands}}
\date{October 1, 2005}

\begin{document}
\maketitle
\hyphenation{semi-biplane}

\begin{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.
\end{abstract}

\section{Introduction}
A {\em $(0,2)$-graph} is a connected graph such that
any two vertices have either 0 or 2 common neighbours.
A {\em rectagraph} is a $(0,2)$-graph without triangles.
A {\em 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 \cite{Hu}
in the study of projective planes with involution,
and are the topic of the thesis \cite{Wt} of Peter Wild.
Rectagraphs were introduced by Arnold Neumaier \cite{N}
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 \cite{Mu} showed that $(0,2)$-graphs are regular,
say of valency $k$, and that the number $v$ of vertices
and the diameter $d$ satisfy $v \le 2^k$ and $d \le 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 \cite{W} determined
all semi\-biplanes of block size at most 6. Michel Mollard \cite{Mo}
determined all $(0,2)$-graphs on at most 31 vertices (and finds that
these have valency at most 7).

\section{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$.

\section{Doubling}

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

This shows that non-bipartite $(0,2)$-graphs of valency $k$
satisfy $v \le 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 $\Delta$ with
involutory automorphism $\sigma$ without fixed edges
that interchanges the two classes of the bipartition,
one can construct a $(0,2)$-graph $\Gamma = \Delta/\sigma$
that has the $\sigma$-orbits as vertices, where two $\sigma$-orbits are
adjacent when there are edges between them.

In terms of semibiplanes, $\sigma$ 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 semi\-biplanes of small block size,
and finding their polarities.

\medskip
The {\em extended bipartite double} of a graph $\Gamma$
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 $\Gamma$ is just the product $K_2 \times \Gamma$.

\medskip
The {\em 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.

\section{Products}
Let us use the symbol $\sim$ to denote adjacency.

For graphs $\Gamma$ and $\Delta$, let $\Gamma \times \Delta$
be the graph of which the vertex set is the Cartesian product
of the vertex sets of $\Gamma$ and $\Delta$, where
$(x,y) \sim (x',y')$ whenever either $x = x'$ and $y \sim y'$
or $x \sim x'$ and $y = y'$.

If $\Gamma$ and $\Delta$ are $(0,2)$-graphs, then also
$\Gamma \times \Delta$ is one. And if both are bipartite,
then so is $\Gamma \times \Delta$.
The valency of $\Gamma \times \Delta$
is the sum of the valencies of $\Gamma$ and $\Delta$.
The diameter of $\Gamma \times \Delta$
is the sum of the diameters of $\Gamma$ and $\Delta$.

The hypercube $2^k$ (also called $Q_k$) is $\times_{i=1}^k K_2$.

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

If $\Gamma$ 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 $\Gamma/G$ is a
$(0,2)$-graph.

In case $G = \langle \sigma \rangle$ we write $\Gamma/\sigma$
instead of $\Gamma/G$.

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

Let $\delta$ be the automorphism of $\Gamma$ that interchanges
$(u,x^+)$ and $(u,x^-)$ for all $u$ and $x$. The $\tau = \sigma \delta$
is an automorphism of $\Gamma$ that sends each vertex to a vertex at
distance 5, and $\Gamma / \tau$ is a nonbipartite rectagraph
with 48 vertices, valency 7 and group of order 960.
(It is $\Gamma_{7.44}$.)

\section{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 = \langle 1110000, 0111111 \rangle$,
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$.

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 \cite{BCN}, 4.3.6 and 4.3.8.

\section{Nonbipartite quotients of a hypercube}

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

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

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

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

(Indeed, choose the vector $a$ so that the support of $a+\pi(a)+u$ is fixed
pointwise by $\pi$. Then $x \mapsto \pi(x+a) + u + a$ is the required
conjugate.)

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

\section{Nonbipartite quotients of a folded hypercube}

If $k$ is even, then the quotient $2^k / {\bf 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 \mapsto \pi(x) + u$
where $\pi \in {\rm Sym}(k)$ is a coordinate permutation of order 1 or 2
and $u \in 2^k$ is a vector of odd weight, and either
$\pi(u) = u + {\bf 1}$, or $\pi(u) = u$ where $\pi$ fixes at least
three coordinates inside and three coordinate outside the support of $u$.

In particular, for $k = 6$ we can use either $\pi = 1$, $u = (000111)$
and find $K_4 \times K_4$, or $\pi = (12)(34)(56)$, $u = (010101)$
and find the Shrikhande graph.

\section{Quotients of projective planes}
Given a projective plane $\Pi$ with involution $\sigma$,
construct a semibiplane of which the points and blocks
are the $\sigma$-orbits of size 2 on the points and blocks of $\Pi$
(Hughes \cite{Hu}). If $\Pi$ has parameters $PG(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 \cite{Mh} on reconstructing $\Pi$
given the semibiplane $\Pi/\sigma$.

\section{The half-double of a locally bipartite graph}
Let $\Gamma$ be a graph, and assume that for each vertex $x$ a partition $\Pi_x$
of the set of neighbours of $\Gamma$ is given. Then we can define a graph $\Delta$
by taking as vertices the pairs $(x,\pi)$ where $\pi \in \Pi_x$, and letting
$(x,\pi)$ be adjacent to $(y,\rho)$ when $y \in \pi$ and $x \in \rho$.

The resulting graph $\Delta$ has the same number as edges as $\Gamma$,
and the covering map $(x,\pi) \mapsto x$ sends edges to edges.

Now let $\Gamma$ 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 $\Delta$, called the
{\em half-double} of $\Gamma$ (with twice as many vertices and the same number
of edges). Note that $\Delta$ need not be connected, even when $\Gamma$ is.

Apply this construction to the strongly regular graph with parameters
$(v,k,\lambda) = (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 $\Gamma$ again.
This graph has automorphism group $U_3(3).2$ with point stabilizer $L_2(7)$.
(It is $\Delta_{7.29}$.)

\section{A cover}\label{cover1152}
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 \times K_4$ on 64 vertices with $k = 7$.
Let the vertex set be $A \times A \times B \times B$, where
$A = \Zz_3 \cup \{\infty\}$ and $B = \Zz_2$.
Let the adjacencies be
$(a,b,0,j) \sim (a,c,1,j+f(a,b,c))$ and
$(a,b,0,j) \sim (c,b,1,j+f(b,a,c))$ for $a,b,c \in A$ and $j \in B$,
where $f(a,b,c) = 1$ for $a = \infty$, $b \ne \infty$, $c = b-1$ or $c = b$,
and for $a \ne \infty$, $b \ne \infty$, $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 $\Delta_{7.22}$.)

\section{A $(0,2)$-graph from the dodecahedron}\label{dodec02}
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 edge-disjoint union of the dodecahedron graph
and $5K_4$, each of valency 3.) The resulting graph is $\Gamma_{6.8}$.

\section{Semibiplanes with $k \le 7$}

We find unique bipartite $(0,2)$-graphs of valency $k$ for $k \le 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 \"Osterg{\aa}rd independently verified these numbers,
and went on to do $k = 8$.)

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 \le k \le 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 $\Delta_{k.i}$.

\medskip{\footnotesize
\tablehead{
\# & $k$ & $v$ & $d$ & distribution & gsz & orbits & graph \\
\hline}
\tabletail{\hline}
\noindent\begin{supertabular}{|r|rrrlrlll}
1 & 0 & 1 & 0 & 1 & 1 & tra & $2^0$ \\
\hline
1 & 1 & 2 & 1 & 1+1 & 2 & tra & $2^1$ \\
\hline
1 & 2 & 4 & 2 & 1+2+1 & 8 & tra & $2^2$ \\
\hline
1 & 3 & 8 & 3 & 1+3+3+1 & 48 & tra & $2^3$ \\
\hline
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$ \\
\hline
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 \times \Delta_{4.1}$ \\
4 & 5 & 32 & 5 & 1+5+10+10+5+1 & 3840 & tra & $2^5$ \\
\hline
% k=6: 18 local situations, 13 graphs
1 & 6 & 32 & 3 & 1+6+15+10 & 1536 & tra & 2-(16,6,2)                 \\ % 95
2 & 6 & 32 & 3 & 1+6+15+10 & 768 & tra & 2-(16,6,2)                  \\ % 96
3 & 6 & 32 & 3 & 1+6+15+10 & 23040 & tra & 2-(16,6,2), $2^6/{\bf 1}$ \\ % 108
4 & 6 & 36 & 4 & 1+6+15+12+2 & 96 & 12+24 &                          \\ % 27
5 & 6 & 36 & 4 & 1+6+15+12+2 & 4320 & tra &
 drg \cite{JT},\cite[p.399]{BCN}                                     \\ % 38
6 & 6 & 36 & 4 & 1+6+15+12+2 & 48 & 12+24 &                          \\ % 71
7 & 6 & 40 & 4 & 1+6+15+14+4 & 48 & 8+8+24 &                         \\ % 23
8 & 6 & 40 & 4 & 1+6+15+14+4 & 120 & tra &                           \\ % 78
9 & 6 & 44 & 4 & 1+6+15+16+6 & 2640 & tra & $2 \times \Delta_{5.1}$  \\ % 47
10 & 6 & 48 & 5 & 1+6+15+18+8 (32x) & 256 & 16+32 &                  \\ % 1
   &   &    &   & 1+6+15+17+8+1 (16x) \\
11 & 6 & 48 & 5 & 1+6+15+17+8+1 & 960 & tra & $2 \times \Delta_{5.2}$\\ % 50
12 & 6 & 56 & 5 & 1+6+15+19+12+3 & 2688 & tra & $2^2 \times \Delta_{4.1}$\\ % 20
13 & 6 & 64 & 6 & 1+6+15+20+15+6+1 & 46080 & tra & $2^6$             \\ % 107
\hline
1 & 7 & 48 & 4 & 1+7+21+17+2 & 384 & tra \\                % 0767
2 & 7 & 48 & 4 & 1+7+21+17+2 & 1920 & tra & $\Delta_{7.38}/\sigma$, see \S5 \\ % 0932
3 & 7 & 48 & 4 & 1+7+21+17+2 & 48 & tra \\                 % 3031
4 & 7 & 48 & 4 & 1+7+21+17+2 & 64 & 16+32 \\               % 3032
5 & 7 & 48 & 4 & 1+7+21+17+2 & 64 & 16+32 \\               % 3083
6 & 7 & 48 & 4 & 1+7+21+17+2 & 48 & tra \\                 % 3091
7 & 7 & 48 & 4 & 1+7+21+17+2 & 96 & tra \\                 % 3252
8 & 7 & 48 & 4 & 1+7+21+17+2 & 72 & 12+36 \\               % 3257
9 & 7 & 48 & 4 & 1+7+21+17+2 & 96 & tra \\                 % 3392
10 & 7 & 48 & 4 & 1+7+21+17+2 & 2016 & tra & $\Pi / \sigma$ \\ % 3435
11 & 7 & 56 & 4 & 1+7+21+21+6 & 16 & 2*4+2*8+2*16 \\        % 0769
12 & 7 & 56 & 4 & 1+7+21+21+6 & 8 & 4*4+5*8 \\              % 0770
13 & 7 & 56 & 4 & 1+7+21+21+6 & 16 & 2*4+2*8+2*16 \\        % 0771
14 & 7 & 56 & 4 & 1+7+21+21+6 & 24 & 2+6+4*12 \\            % 0812
15 & 7 & 56 & 4 & 1+7+21+21+6 & 8 & 4*4+5*8 \\              % 0814
16 & 7 & 56 & 4 & 1+7+21+21+6 & 4 & 14*4 \\                 % 1792
17 & 7 & 56 & 4 & 1+7+21+21+6 & 16 & 3*8+2*16 \\            % 1802
18 & 7 & 64 & 4 & 1+7+21+25+10 & 48 & 16+48 \\              % 1032
19 & 7 & 64 & 4 & 1+7+21+25+10 & 120 & 24+40 \\             % 1040
20 & 7 & 64 & 4 & 1+7+21+25+10 & 3072 & tra & $2 \times \Delta_{6.1}$ \\ % 2712
21 & 7 & 64 & 4 & 1+7+21+25+10 & 1536 & tra & $2 \times \Delta_{6.2}$ \\ % 2713
22 & 7 & 64 & 4 & 1+7+21+25+10 & 1152 & tra & see \S\ref{cover1152} \\   % 3765
23 & 7 & 64 & 4 & 1+7+21+25+10 & 46080 & tra & $2 \times \Delta_{6.3}$ \\% 3769
24 & 7 & 64 & 5 & 1+7+21+25+10 (60x) & 12 & 4+5*12 \\       % 0773
   &   &    &   & 1+7+21+24+10+1 (4x) \\
25 & 7 & 64 & 5 & 1+7+21+24+10+1 (36x) & 24 & 4+5*12 \\     % 0797
   &   &    &   & 1+7+21+25+10 (28x) \\
26 & 7 & 64 & 5 & 1+7+21+24+10+1 (24x) & 8 & 8*4+4*8 \\     % 0804
   &   &    &   & 1+7+21+25+10 (40x) \\
27 & 7 & 64 & 5 & 1+7+21+24+10+1 (14x) & 12 & 2*2+2*6+4*12 \\ % 1018
   &   &    &   & 1+7+21+25+10 (50x) \\
28 & 7 & 64 & 5 & 1+7+21+24+10+1 (8x) & 336 & 8+56 \\       % 3299
   &   &    &   & 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)$ \\      % 0001
30 & 7 & 72 & 5 & 1+7+21+27+14+2 & 192 & 24+48 & $2 \times \Delta_{6.4}$ \\  % 1007
31 & 7 & 72 & 5 & 1+7+21+27+14+2 & 8640 & tra & $2 \times \Delta_{6.5}$ \\   % 1207
32 & 7 & 72 & 5 & 1+7+21+27+14+2 & 96 & 24+48 & $2 \times \Delta_{6.6}$ \\   % 2628
33 & 7 & 80 & 5 & 1+7+21+30+18+3 (32x) & 48 & 8+24+48 \\                     % 0002
   &   &    &   & 1+7+21+31+18+2 (48x) \\
34 & 7 & 80 & 5 & 1+7+21+29+18+4 & 96 & 16+16+48 & $2 \times \Delta_{6.7}$ \\   % 0997
35 & 7 & 80 & 5 & 1+7+21+29+18+4 & 240 & tra & $2 \times \Delta_{6.8}$ \\       % 2645
36 & 7 & 88 & 5 & 1+7+21+31+22+6 & 10560 & tra & $2^2 \times \Delta_{5.1}$ \\   % 1424
37 & 7 & 96 & 6 & 1+7+21+32+25+9+1 (32x) & 512 & 32+64 & $2 \times \Delta_{6.10}$\\
   &   &    &   & 1+7+21+33+26+8 (64x) \\                                       % 0091
38 & 7 & 96 & 6 & 1+7+21+32+25+9+1 & 3840 & tra & $2^2 \times \Delta_{5.2}$\\   % 1449
39 & 7 & 112 & 6 & 1+7+21+34+31+15+3 & 16128 & tra & $2^3 \times \Delta_{4.1}$\\% 0760
40 & 7 & 128 & 7 & 1+7+21+35+35+21+7+1 & 645120 & tra & $2^7$ \\ % 9999
\end{supertabular}}

\medskip
The above table contains five pairs of graphs for which identical data is given.
Given a vertex $x$ of a $(0,2)$-graph $\Gamma$ 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 $\Delta_{7.i}$ with $1 \le i \le 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 $\Delta_{7.i}$ with $11 \le i \le 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.

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

\section{Nonbipartite $(0,2)$-graphs with $k \le 7$}
The nonbipartite $(0,2)$-graphs with $k \le 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 \times 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.)
% When not all local graphs are isomorphic, frequencies are given.
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, $\phi$ denotes
the interchange of antipodal vertices.

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

\medskip{\footnotesize
\tablehead{
\# & bipd & $k$ & $v$ & $d$ & distribution & locally & gsz & orbits & graph \\
\hline}
\tabletail{\hline}
\noindent\begin{supertabular}{|r|r|rrrllrll}
1 & 3.1 & 3 & 4 & 1 & 1+3 & C3 & 24 & tra & $2^3 / (111) \cong K_4$ \\
\hline
1 & 4.2 & 4 & 8 & 2 & 1+4+3 & C31 & 48 & tra & $2^4 / (0111) \cong K_2 \times K_4$ \\
\hline
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) \cong 2^2 \times K_4$ \\
4 & 5.4 & 5 & 16 & 3 & 1+5+7+3 (8x) & C311 & 96 & 8+8 & $2^5/\pi_{(12)}(00111)$ \\
  &     &   &    &   & 1+5+10 (8x) & C11111 \\
\hline
1 & 6.3 & 6 & 16 & 2 & 1+6+9 & C33 & 1152 & tra & $K_4 \times K_4$ \\ % s6.0108.q0001
2 & 6.3 & 6 & 16 & 2 & 1+6+9 & C6 & 192 & tra & Shrikhande \\ % s6.0108.q0011
3 & 6.8 & 6 & 20 & 3 & 1+6+12+1 & C3111 & 60 & tra & \S\ref{dodec02} \\ % s6.0078.q0001
4 & 6.7 & 6 & 20 & 3 & 1+6+10+3 (12x) & C51 & 24 & 4+4+12 & \\ % s6.0023.q0001
&  &   &    &   & 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 & \\ % s6.0050.q0001
&  &   &    &   & 1+6+15+2 (8x) & C111111 \\
6 & 6.11 & 6 & 24 & 3 & 1+6+15+2 & recta & 480 & tra & $(2\times{\rm bipd}({\rm ico}))/\phi$\\ % s6.0050.q0018
7 & 6.11 & 6 & 24 & 4 & 1+6+10+6+1 & C51 & 240 & tra & $2 \times \Gamma_{5.1}$ \\ % s6.0050.q0007
8 & 6.12 & 6 & 28 & 3 & 1+6+12+9 (16x) & C3111 & 48 & 4+12+12 & \\ % s6.0020.q0001
  &&   &    &   & 1+6+15+6 (12x) & C111111 \\
9 & 6.13 & 6 & 32 & 3 & 1+6+15+10 & recta & 3840 & tra & $2 \times \Gamma_{5.2}$ \\ % s6.0107.q0091
10 & 6.13 & 6 & 32 & 4 & 1+6+12+10+3 & C3111 & 1152 & tra & $2^3 \times K_4$ \\ % s6.0107.q0001
11 & 6.13 & 6 & 32 & 4 & 1+6+12+10+3 (16x) & C3111 & 192 & 16+16 & $2 \times \Gamma_{5.4}$\\
   &&   &    &   & 1+6+15+10 (16x) & C111111 \\ % s6.0107.q0002
\hline
1 & 7.1 & 7 & 24 & 2 & 1+7+16 & C511 & 96 & tra       \\ % s7.0767.q0001
2 & 7.1 & 7 & 24 & 2 & 1+7+16 & C511 & 96 & tra       \\ % s7.0767.q0003
3 & 7.2 & 7 & 24 & 2 & 1+7+16 & C511 & 480 & tra      \\ % s7.0932.q0010
4 & 7.2 & 7 & 24 & 2 & 1+7+16 & C511 & 480 & tra      \\ % s7.0932.q0020
5 & 7.1 & 7 & 24 & 3 & 1+7+15+1 & C331 & 96 & tra     \\ % s7.0767.q0005
6 & 7.2 & 7 & 24 & 3 & 1+7+15+1 & C61 & 48 & tra      \\ % s7.0932.q0001
7 & 7.4 & 7 & 24 & 3 & 1+7+14+2 (4x) & C7 & 8 & 4*4+8 \\ % s7.3032.q0001
&&&&& 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 \\ % s7.3083.q0001
&&&&& 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 \\    % s7.3091.q0001
&&&&& 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 \\ % s7.3257.q0001
&&&&& 1+7+15+1 (12x) & C61 \\
11 & 7.9 & 7 & 24 & 3 & 1+7+16 (12x) & C511 & 12 & 4*6 \\ % s7.3392.q0001
&&&&& 1+7+15+1 (12x) & C61 \\
12 & 7.10 & 7 & 24 & 3 & 1+7+14+2 & C7 & 336 & tra & drg \cite[p.386]{BCN} \\ % s7.3435.q0001, Klein
13 & 7.24 & 7 & 32 & 3 & 1+7+18+6 (12x) & C31111 & 6 & 2+5*6 \\ % s7.0773.q0001
&&&&& 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 \\ % s7.0804.q0001
&&&&& 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 \\ % s7.1018.q0001
&&&&& 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 \\ % s7.1032.q0001
&&&&& 1+7+15+9 (8x) & C61 \\
17 & 7.18 & 7 & 32 & 3 & 1+7+18+6 & C31111 & 24 & 8+24 \\ % s7.1032.q0003
18 & 7.20 & 7 & 32 & 3 & 1+7+18+6 & C31111 & 512 & tra \\ % s7.2712.q0001
19 & 7.20 & 7 & 32 & 3 & 1+7+18+6 & C31111 & 256 & tra \\ % s7.2712.q0004
20 & 7.21 & 7 & 32 & 3 & 1+7+18+6 & C31111 & 96 & tra \\ % s7.2713.q0001
21 & 7.21 & 7 & 32 & 3 & 1+7+18+6 & C31111 & 768 & tra \\ % s7.2713.q0002
22 & 7.28 & 7 & 32 & 3 & 1+7+21+3 (4x) & C1111111 & 24 & 4+4+24 \\ % s7.3299.q0001
&&&&& 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 \\ % s7.3299.q0011
&&&&& 1+7+15+9 (28x) & C61 \\
24 & 7.22 & 7 & 32 & 3 & 1+7+16+8 (24x) & C511 & 48 & 8+24 \\ % s7.3765.q0001
&&&&& 1+7+15+9 (8x) & C61 \\
25 & 7.23 & 7 & 32 & 3 & 1+7+18+6 & C31111 & 1536 & tra & $2^7 / C$, see \S6 \\ % s7.3769.q0001
26 & 7.23 & 7 & 32 & 3 & 1+7+18+6 & C31111 & 256 & tra \\ % s7.3769.q0002
27 & 7.23 & 7 & 32 & 3 & 1+7+15+9 & C331 & 2304 & tra & $2 \times \Gamma_{6.1}$ \\ % K2 x K4 x K4, s7.3769.q0012
28 & 7.23 & 7 & 32 & 3 & 1+7+15+9 & C61 & 384 & tra & $2 \times \Gamma_{6.2}$ \\ % K2 x Shrikhande, s7.3769.q0093
29 & 7.25 & 7 & 32 & 4 & 1+7+16+7+1 (6x) & C511 & 12 & 2+5*6 \\ % s7.0797.q0001
&&&&& 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 \\ % s7.3299.q0002
&&&&& 1+7+16+8 (28x) & C511 \\
31 & 7.30 & 7 & 36 & 3 & 1+7+18+10 (20x) & C31111 & 32 & 4+2*8+16 \\ % s7.1007.q0001
&&&&& 1+7+21+7 (16x) & C1111111 \\
32 & 7.32 & 7 & 36 & 3 & 1+7+18+10 (20x) & C31111 & 8 & 3*4+3*8 \\ % s7.2628.q0001
&&&&& 1+7+21+7 (16x) & C1111111 \\
33 & 7.34 & 7 & 40 & 4 & 1+7+16+13+3 (24x) & C511 & 48 & 8+8+24 & $2 \times \Gamma_{6.4}$ \\ % s7.0997.q0001
&&&&& 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 \\ % s7.0997.q0002
&&&&& 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 \\ % s7.2645.q0001
&&&&& 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 \times \Gamma_{6.3}$ \\ % s7.2645.q0005
37 & 7.36 & 7 & 44 & 3 & 1+7+18+18 (20x) & C31111 & 80 & 4+20+20 \\ % s7.1424.q0001
&&&&& 1+7+21+15 (24x) & C1111111 \\
38 & 7.37 & 7 & 48 & 4 & 1+7+21+19 (16x) & C1111111 & 32 & 3*16 \\ % s7.0091.q0001
&&&&& 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 \\ % s7.0091.q0002
&&&&& 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 \\ % s7.0091.q0006
&&&&& 1+7+21+17+2 (32x) & C1111111 \\
41 & 7.38 & 7 & 48 & 4 & 1+7+18+17+5 (32x) & C31111 & 64 & 16+32 & $2 \times \Gamma_{6.5}$ \\ % s7.1449.q0001
&&&&& 1+7+21+17+2 (16x) & C1111111 \\
42 & 7.38 & 7 & 48 & 4 & 1+7+18+19+3 (24x) & C31111 & 96 & 24+24 \\ % s7.1449.q0002
&&&&& 1+7+21+19 (24x) & C1111111 \\
43 & 7.38 & 7 & 48 & 4 & 1+7+18+19+3 (16x) & C31111 & 64 & 3*16 \\ % s7.1449.q0004
&&&&& 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 & $\Delta_{7.38}/\tau$, see \S5 \\ % s7.1449.q0068
45 & 7.38 & 7 & 48 & 4 & 1+7+21+17+2 & recta & 960 & tra & $2 \times \Gamma_{6.6}$ \\       % s7.1449.q0072
46 & 7.38 & 7 & 48 & 5 & 1+7+16+16+7+1 & C511 & 960 & tra & $2^2 \times \Gamma_{5.1}$ \\    % s7.1449.q0016
47 & 7.38 & 7 & 48 & 5 & 1+7+16+16+7+1 (24x) & C511 & 480 & 24+24 \\                        % s7.1449.q0024
&&&&& 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 \times \Gamma_{6.8}$ \\ % s7.0760.q0001
&&&&& 1+7+21+21+6 (24x) & C1111111 \\
49 & 7.39 & 7 & 56 & 4 & 1+7+18+21+9 & C31111 & 8064 & tra & $K_4 \times \Delta_{4.1}$ \\ % s7.0760.q0012
50 & 7.39 & 7 & 56 & 4 & 1+7+18+21+9 (24x) & C31111 & 384 & 8+16+32 \\ % s7.0760.q0017
&&&&& 1+7+21+24+3 (32x) & C1111111 \\
51 & 7.40 & 7 & 64 & 3 & 1+7+21+35 & recta & 322560 & tra & $2^7/(1111111)$ \\ % s7.9999.q0939
52 & 7.40 & 7 & 64 & 4 & 1+7+21+25+10 & recta & 15360 & tra & $2^2 \times \Gamma_{5.2}$ \\ % s7.9999.q0117
53 & 7.40 & 7 & 64 & 4 & 1+7+21+25+10 (32x) & recta & 7680 & 32+32 & $2^7/\pi_{(12)} \cdot$ \\
&&   &    &   & 1+7+21+35 (32x) &          &      &       & \quad$\cdot (0011111)$ \\ % s7.9999.q0122
54 & 7.40 & 7 & 64 & 5 & 1+7+18+22+13+3 & C31111 & 9216 & tra & $2^4 \times K_4$ \\ % s7.9999.q0001
55 & 7.40 & 7 & 64 & 5 & 1+7+18+22+13+3 (32x) & C31111 & 768 & 32+32 & $2^2 \times \Gamma_{5.4}$ \\ % s7.9999.q0002
&&&&& 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/\pi_{(12)(34)} \cdot$ \\
&&  &   &    & 1+7+21+25+10 (32x) & C1111111 &     &         & \quad$\cdot (0000111)$ \\ % s7.9999.q0005
&&&&& 1+7+21+35 (16x) & C1111111 \\
\end{supertabular}}

\medskip
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 \times K_3$ on each edge across, namely 3, 2, 5, 0 for the for cases
$\Gamma_{7.i}$, $i=1,2,3,4$, respectively.

\begin{thebibliography}{}

\bibitem{BCN} A. E. Brouwer, A. M. Cohen \& A. Neumaier,
{\it Distance-regular graphs},
Springer, Berlin, 1989.

\bibitem{Hu} D. R. Hughes,
{\it 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.

\bibitem{JT} Zvonimir Janko \& Tran Van Trung,
{\it Two new semibiplanes},
J. Combin. Theory Ser. A {\bf 33} (1982) 102--105.

\bibitem{Mo} Michel Mollard,
{\it Table of (0,2)-graphs of order less than 32},
Rapport de Recherche/IMAG RR 939, Grenoble, June 1994.

\bibitem{Mh} G. Eric Moorhouse,
{\it 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.

\bibitem{Mu} H. M. Mulder,
{\it The interval function of a graph},
PhD thesis, Vrije Universiteit Amsterdam, 1980.

\bibitem{N} A. Neumaier,
{\it 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.

\bibitem{Wt} P. R. Wild,
{\it On semibiplanes}, Ph.D. Thesis, University of London, 1980.

\bibitem{W} Peter Wild,
{\it Generalized Hussain graphs and semibiplanes with $k\leq 6$},
Ars Combin. {\bf 14} (1982) 147--167.

\end{thebibliography}

\end{document}

\bibitem{Ba2} B. Baumeister,
{\it On flag-transitive c.c∗-geometries},
in: Proceeedings of the Ohio State Conference (May 1993),
ed. by K.T. Arasu et al., pp. 3-–23.

\bibitem{Wf} Peter Wild,
{\it Some families of semibiplanes},
Discr. Math. {\bf 138} (1995) 397--403.

Coulter, Robert S.(5-QLD-DMC); Henderson, Marie(5-QLD-DMC)
   A class of functions and their application in constructing semi-biplanes and
   association schemes. (English. English summary)
   Discrete Math. 202 (1999), no. 1-3, 21--31.

% What about nonbipartite quotients of a product?
