%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% A LaTeX file for a four page document
%
%
%
\documentclass[12pt]{article}
\textwidth=6.2in
\textheight=8.5in
\oddsidemargin=0pt
\evensidemargin=0pt
\topmargin=0pt
\begin{document}
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics \textbf{7} (2000),
\#R22\hfill}
\thispagestyle{empty}
%
\title{The Strongly Regular $(40,12,2,4)$ Graphs}
\author{
E. Spence\\
Department of Mathematics\\
University of Glasgow\\
Glasgow G12 8QQ\\
Scotland\\
{\small\texttt ted@maths.gla.ac.uk}\\
Submitted: May 29, 1998; Accepted: April 20, 2000}
\date{}
%
%
\maketitle
\bibliographystyle{plain}
\begin{abstract}
In a previous paper it was established that there are at least $27$
non-isomorphic strongly regular $(40,12,2,4)$ graphs. Using a different
and more efficient method we have re-investigated these graphs and have
now been able to determine them {\em all}, and so complete the
classification. We have discovered that there are precisely $28$
non-isomorphic $(40,12,2,4)$ strongly regular graphs. The one that was not
found in the previous investigation is characterised uniquely by the fact
that every neighbour graph is triangle-free.
%
%
%
\smallskip
\noindent
{{\em Key words and phrases\/}: Strongly regular graph, classification
\hfill}\\
{{\em AMS subject classifications\/}: Primary 05B05.}
%
\end{abstract}
%
%
\newpage
\begin{section}{Introduction}
A strongly regular $(40,12,2,4)$ graph is a regular graph on $40$
vertices of degree $12$ such that each pair of adjacent vertices has $2$
common neighbours, and each pair of non-adjacent neighbours has $4$
common neighbours.
In \cite{Spe90} an incomplete enumeration of strongly regular
$(40,12,2,4)$ graphs established the existence of at least $27$, all of
which have at least one vertex $x$ whose neighbour graph (the subgraph
induced by the vertices adjacent to $x$)
possesses a
triangle. In the intervening years, computers have speeded up
considerably, and this fact has aided the completion of the
classification.
Running the same program that was used in \cite{Spe90}
the author has discovered that there are in fact $28$ such strongly
regular graphs, so only one graph is missing from the
original list. As a means of verifying the result a different search
method was used. It is this that we describe briefly in the next
section.
The author is grateful to Brendan McKay for a further different and
independent corroboration of the final result \cite{BM99}.
\section{The method}
As was first pointed out in
\cite{Haem80}, in any strongly regular $(40,12,2,4)$ graph
$\Gamma$ the neighbour
graph of a vertex $x$
is one of the
following five types:
\begin{enumerate}
{\em
\item a $12$-cycle,
\item the disjoint union of a $9$-cycle and a triangle,
\item the disjoint union of two $6$-cycles,
\item the disjoint union of a $6$-cycle and two triangles,
\item the disjoint union of four triangles.
}\end{enumerate}
One method of classifying the strongly regular graphs might be to start
with one of the above neighbour graphs and attempt to extend it to an
SRG on $40$ vertices by first filling in the possible adjacencies
between the neighbours and non-neighbours of a given vertex. However,
in general there were very many such possibilities and for each such
there were again many ways, at least in the beginning, of assigning
adjacencies among the non-neighbours. An improvement on this idea was
obtained by first extending each neighbour graph to a larger subgraph,
using the eigenvalues of the SRG to limit the number of possibilities.
We make the observation that $\Gamma$ has eigenvalues
$12^1, 2^{24}$ and $-4^{15}$ (exponents denote multiplicities),
and that these are interlaced by the
eigenvalues of any subgraph. See \cite{Haem80} for details on the
interlacing of eigenvalues.
It follows readily that if $\Gamma$ has
adjacency matrix $A$, then
\[ J - 4(A-2I), \]
where $J$ and $I$ are the all-one and identity matrix, respectively,
is positive semi-definite, with eigenvalues $0^{25}, 24^{15}$. Thus, if
$B$ is any principal sub-matrix of $A$, then
\[ J - 4(B-2I) \]
has rank at most $15$, and all its eigenvalues $\lambda$ satisfy
$0\le \lambda \le 24$.
Consider a vertex $x$ with neighbour graph $\Gamma_x$ one of the above
five types, and take a vertex $y$, non-adjacent to $x$. This too will
have a neighbour graph $\Gamma_y$, also one of the five types. These two
vertices, together with their neighbours, induce a subgraph $\Delta$
on $22$
vertices, whose adjacency matrix $B$ say, must satisfy the
conditions above.
An intermediate step in the classification of the strongly regular
graphs was initially to determine all such subgraphs and then to attempt
to embed them in the full graph on $40$ vertices. We describe briefly
this initial step. The two vertices $x$ and $y$ have $4$ common
neighbours, and
these might be chosen in ${12\choose 4} = 495$ ways. For each such
choice, and for each of the five choices of $\Gamma_x$, we enumerated
all possible
(non-isomorphic) subgraphs in which $\Gamma_y$ contained the subgraph
on the four common neighbours.
To shorten the computation, we used the standard form of the adjacency
matrix of a graph. This may be described as follows.
Associated with the adjacency matrix of any graph there is
a binary integer obtained by concatenating the rows of the upper
triangular part of the matrix. The {\em standard form\/} of this matrix is
the greatest such integer obtained by permuting the vertices of the
graph.
In searching for the subgraphs $\Gamma_y$ we made the assumption that
the standard form of the adjacency matrix of $\Gamma_x$ was greater than
that of the adjacency matrix of $\Gamma_y$.
By permuting rows and
columns we can assume that the partially completed adjacency matrix
takes the form
\[
\begin{array}{c c}
\begin{array}{c} x \\ y \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\
\end{array} &
\left[
\begin{tabular}{c | c | c c}
0\,0 & 1\,1\,1\,1\,1\,1\,1\,1\,1\,1\,1\,1&0\,0\,0\,0\,0\,0\,0\,0\\
0\,0 & 1\,1\,1\,1\,0\,0\,0\,0\,0\,0\,0\,0 & 1\,1\,1\,1\,1\,1\,1\,1\\
\hline
1\,1 & & \\
1\,1 & & \\
1\,1 & & \\
1\,1 & $\Gamma_x$ & \\
1\,0 & & \\
\vdots\,\vdots & & \\
1\,0 & & \\
\hline
0\,1 & & \\
0\,1 & & \\
\vdots\,\vdots & & $\Gamma'_y$ \\
0\,1 & & \\
0\,1 & & \\
\end{tabular}
\right],
\end{array}
\]
where $\Gamma'_y$ is the subgraph of $\Gamma_y$ on the vertices
adjacent to $y$ but
non-adjacent to $x$. To extend this to a possible candidate subgraph on
$22$ vertices it is now necessary to determine possible adjacencies
between the neighbours of $x$ but not of $y$, and the neighbours of
$y$ but not of $x$.
It was here that the
conditions on the rank and the eigenvalues played important roles.
They were applied at each stage when the neighbours of $y$ but not of
$x$ had been assigned possible neighbours in turn (among the neighbours
of $x$ but not of $y$).
Once all possible subgraphs on $22$ vertices had been determined, it was
a relatively easy (and quick) task to extend these, where possible, to
a completed strongly regular graph.
This method, as described briefly above, turned out to be many times
quicker than that used in \cite{Spe90}, where the search was
incomplete. Even allowing for the increase
in the speed of computers in the intervening years, the fact that the
total CPU time of the present search was less than $4$ hours on a
Pentium III running at $600$ MHz, represents a substantial improvement.
\begin{table}
\[
\begin{tabular}{|c|c|c|}
\hline
Nbr. graph & No. subgraphs & No. SRG's \cr
\hline\hline
$1$ &$434$ &$18$ \cr\hline
$2$ &$1023$ & $21$ \cr\hline
$3$ &$367$ &$14$ \cr\hline
$4$ &$895$ &$20$ \cr\hline
$5$ &$165$ &$23$ \cr\hline\hline
\end{tabular}
\]
\caption{}
\end{table}
In Table 1 we list the number of non-isomorphic subgraphs obtained
corresponding to each of the neighbour graphs $1,2,3,4$ and $5$,
together with the number of non-isomorphic strongly regular graphs that
were constructed by extending these subgraphs. As mentioned in the
Introduction, the final number of non-isomorphic $(40,12,2,4)$ SRG's is
$28$. Of these there is precisely one for which the neighbour graph of
every vertex has no triangles. It is the one that is missing from the
original investigation of \cite{Spe90}.
All these graphs, and some data concerning their structure, namely,
generators of their automorphism groups, the orbits under the action of
the automorphism group and the distribution of the five types of
neighbour graphs, can be found in the accompanying file.
\end{section}
\def\={$\,$}
\begin{thebibliography}{00}
\frenchspacing
\bibitem{Haem80}
W.\=H.\=Haemers,
Eigenvalue Techniques in Design and Graph Theory,
{\it Mathematical Centre Tracts 121},
Mathematisch Centrum,
Amsterdam, (1980).
\bibitem{BM99} B.\=D.\=McKay,
Private communication (1999).
\bibitem{Spe90}
E.\=Spence,
$(40,13,4)$ designs derived from strongly regular graphs,
{\it Advances in Finite Geometry and Designs},
Oxford University Press, (1990), 359--368.
\nonfrenchspacing
\end{thebibliography}
\end{document}