\documentclass[12pt]{article}
\usepackage{e-jc}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{appendix}
\usepackage{enumerate}
\usepackage{amsmath}

\input amssym.def 
\input amssym.tex 

\newcounter{constructor}
\setcounter{constructor}{0}

\newcommand{\Constr}[2]{
\hypertarget{#1}{}
\medskip
\noindent
\addtocounter{constructor}{1}{\bf Construction \Roman{constructor}. \hspace{3mm} #2}
}

\newcommand{\Record}[4]{
\bigskip
\hypertarget{#1}{
\noindent
{\bf Rec(#2,#3) = #4}
}
\medskip
}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}

\date{\dateline{May XX, 2008}{Sep XX, 2008}\\
\small Mathematics Subject Classifications: 05C35,05C25}

\begin{document}

\title{Dynamic Cage Survey}

\author{
Geoffrey Exoo \\
Department of Mathematics and Computer Science \\
Indiana State University \\
Terre Haute, IN 47809 \\
ge@cs.indstate.edu
\and
Robert Jajcay \\
Department of Mathematics and Computer Science \\
Indiana State University \\
Terre Haute, IN 47809 \\
robert.jajcay@indstate.edu \medskip \\
Department of Algebra \\
Comenius University \\
Bratislava, Slovakia \\
robert.jajcay@fmph.uniba.sk
}

\maketitle

\begin{abstract}
A $(k,g)$-cage is a $k$-regular graph of girth $g$ of minimum order.
In this survey, we present the results of over $50$ years of
searches for cages.
We present the important theorems,
list all the known cages,
compile tables of current 
record holders, and
describe in some detail
most of the relevant constructions.

\end{abstract}

\newpage

\tableofcontents

\newpage

\section{Origins of the Problem}
The cage problem asks for the
construction of regular simple graphs with specified degree and girth
and minimum order.
This problem was first considered by Tutte \cite{tutte}.
A variation of the problem in which the graphs
were required to be Hamiltonian was later studied
by K\'{a}rteszi \cite{karteszi}.
At about the same time,
the study of
Moore graphs, first proposed by E. F. Moore,
was developed by A. J. Hoffman and R. R. Singleton
\cite{hoffsing}.

Their study begins with the observation that
a regular graph of degree $k$ and diameter $d$ has
at most

\begin{equation}
1 + k + k(k-1) + \dots + k(k-1)^{d-1}
\end{equation}
vertices, and
graphs that achieve this bound must
have girth $g = 2d+1$.

One can turn this around and
make a similar observation regarding the
order, $n$, of a regular graph with degree $k$ and
girth $g$. Such a graph is called a {\em $(k,g)$-graph}.
The precise form of the bound on the order $n$ of a
$(k,g)$-graph depends on the parity of $g$:

%% \begin{equation} \label{moore1}
%% n \ge  \left\{ 
%% \begin{array}{lc} 1 + k + k(k-1) + ... + k(k-1)^{(g-3)/2}, & g \mbox{ odd } \\
%%                               2(1 + (k-1) + ... + (k-1)^{(g-2)/2}), & g \mbox{ even } 
%% \end{array}
%% \right.
%% \end{equation}
\begin{align} \label{moore1}
n \ge \left\{
\begin{array}{lccclc} 1 & + & \sum_{i=0}^{(g-3)/2} k(k-1)^i & = & \frac{k(k-1)^{(g-1)/2}-2}{k-2}, & g \mbox{ odd } \\
                & & & & & \\
               & & 2 \sum_{i=0}^{(g-2)/2} (k-1)^i & = & \frac{2(k-1)^{g/2} - 2}{k-2}, & g \mbox{ even }
\end{array}
\right.
\end{align}

\noindent
which is obtained by considering the vertices whose
distance from a given vertex (edge)
is at most $\lfloor (g-1)/2 \rfloor$.

The bound implied by (\ref{moore1})  is called the {\em Moore bound}, and 
is denoted by $M(k,g)$.
Graphs for which equality holds  are called {\em Moore graphs}.  
Moore graphs are relatively rare.

\begin{theorem}[\cite{banito,dam}]
\label{moorebound}

There exists a Moore graph of degree $k$ and girth $g$ if and only if
\begin{description}
\item{(i)} $k=2$ and $ g \geq 3 $, cycles;
\item{(ii)} $g=3$ and $ k \geq 2 $, complete graphs;
\item{(iii)} $g=4$ and $ k \geq 2 $, complete bipartite graphs;
\item{(iv)}  $g = 5$ and: \begin{description}
\item{} \hskip 1cm $k=2$, the $5$-cycle,
\item{} \hskip 1cm $k=3$, the Petersen graph,
\item{} \hskip 1cm $k=7$, the Hoffman-Singleton graph,
\item{} \hskip 1cm and possibly $k=57$;
\end{description}
\item{(v)} $g = 6, 8$, or $12$, and there exists a symmetric generalized
$n$-gon of order $k-1$ (see \ref{geomref}).
\end{description}
\end{theorem}

Regarding {\em (v)},
it should be noted that the only known
symmetric generalized $n$-gons have prime
power order.

The problem of the existence of Moore graphs is closely related to the 
{\em degree/diameter problem} surveyed in \cite{milsir}
(which also contains a further 
discussion of the history of the above theorem).

As Moore graphs do not exist for all parameters, one is
naturally led to consider
the more general problem of determining the minimum order of
$(k,g)$-graphs.
We denote this minimum value by $n(k,g)$ and
refer to a graph that achieves this minimum as
a {\em $(k,g)$-cage}.

In cases where the order of the $(k,g)$-cage is not 
known, we denote the order of the smallest known
$k$-regular graph of girth $g$ by $rec(k,g)$ (the current record holder).

The existence of a $(k,g)$-cage for any pair of parameters $(k,g)$
is not immediately obvious, and it was first shown by Sachs \cite{sachs}.
Almost immediately thereafter, Sachs' upper bound was improved
by Erd\H{o}s, who proved the following theorem in a
joint paper with Sachs \cite{erdossachs}.

\begin{theorem}[\cite{erdossachs}]\label{erdosupper}
For every $ k \geq 2 $, $ g \geq 3 $,
\[
n(k,g) \leq 4 \sum_{t=1}^{g-2} (k-1)^t 
\]
\end{theorem}

The proof in \cite{erdossachs} follows from the stronger assertion of the existence of 
a $k$-regular graph of girth at least $g$ and order $2m$ for every $m \geq 2 \sum_{t=1}^{g-2} (k-1)^t $.
This claim is proved using an interesting induction argument that we present in full in
Appendix \ref{erdproof}.

Curiously enough, the two papers \cite{erdossachs,sachs}
contain two substantially different existence proofs,
while cross-referencing each other.
The proof in \cite{erdossachs} attributed to Erd\H{o}s is
non-constructive. Sachs' proof in \cite{sachs}, on the other hand,
is constructive and uses recursion on the degree.
It so happened that the joint paper \cite{erdossachs} somehow received more
attention, and the natural recursive construction of Sachs was mostly
forgotten. 

To this day, Sachs' result is the only constructive
proof of the existence of
$(k,g)$-graphs for any set of parameters $k \geq 2, g \geq 3$ that is
completely non-algebraic.

An algebraic proof of the existence of $(k,g)$-cages can
be found in Biggs \cite{biggsresid,biggsny}. 
In Section~\ref{cayref} we provide a proof that is a generalization
of Biggs' proof in \cite{biggssurvey}.

\begin{theorem}[\cite{biggssurvey}]\label{biggs-at-least}
For every $k \geq 3$, $g \geq 3$, there is $k$-regular graph $G$ whose girth is at
least $g$.
\end{theorem}

The existence of $k$-regular graphs of girth precisely $g$, for any 
$ k,g \geq 3 $, follows from the above theorem and the following
theorem of Sachs \cite{erdossachs}.

\begin{theorem}[\cite{erdossachs}]\label{sachs-monoton}
Let $G$ have the minimum number of vertices for a $k$-regular graph with girth
at least $g$.  Then the girth of $G$ is exactly $g$.
\end{theorem}

This implies that $n(k,g)$ increases monotonically with $g$.
In this form, the result was also proved later in
\cite{petersenbook} and \cite{fu}.

Another early result of Sachs tying together consecutive odd and even girths 
appears in \cite{erdossachs} and asserts the following:

\begin{theorem}[\cite{erdossachs}]\label{sachs-odd-even}
For every $ k \geq 3 $, and {\em odd} $ g \geq 3 $,
\[ n(k,g+1) \leq 2 n(k,g) \]
\end{theorem}

The easiest proof of this result takes advantage of the voltage graph construction
we describe in Section~\ref{vt-sec}.  This bound has recently been
improved by Balbuena, Gonz\' alez-Moreno and Montellano-Ballesteros:

\begin{theorem}[\cite{balgonmon}]
Let $k \geq 2$ and $g \geq 5$, with $g$ odd.  Then
\[
n(k,g+1) \leq \left\{ 
\begin{array}{lc} 2 n(k,g) - 2 \left(\frac{k(k-1)^{(g-3)/4} - 2}{k-2}\right), & g \equiv 3 \pmod{4} \\
                  2 n(k,g) - 4 \left(\frac{(k-1)^{(g-1)/4} - 1}{k-2}\right), & otherwise.
\end{array}
\right.
\]
\end{theorem}

The upper bound from Theorem \ref{erdosupper} was further improved
by Sauer \cite{sauer}.
His bound is now
commonly referred to as the {\em Sauer bound} and
is given in the following theorem.
Sauer's proof  is constructive and a part of it is similar to the original proof of Erd\H{o}s.
Once again, he constructs a graph of degree $k$, girth $g$,
and order $m$, for every $m$ greater than or equal to his bound.

\begin{theorem}[\cite{sauer}]\label{sauer1}
For every $ k \geq 2 $, $ g \geq 3 $,
\[
n(k,g) \leq \left\{ 
\begin{array}{lc} 2 (k-2)^{g-2}, & g \mbox{ odd, } \\
                  4 (k-1)^{g-3}, & g \mbox{ even. } 
\end{array}
\right.
\]
\end{theorem}

The series of papers \cite{sauer} also contains the following bounds on the 
order of trivalent cages and  two further monotonicity results.

\begin{theorem}[\cite{sauer}] \label{sauer-trivalent}
For every $g \geq 3$,
\[
n(3,g) \leq \left\{ 
\begin{array}{lc} \frac{29}{12} 2^{g-2} + \frac{2}{3}, & g \mbox{ odd, } \\ & \\
                               \frac{29}{12} 2^{g-2} + \frac{4}{3} , & g \mbox{ even. } 
\end{array}
\right.
\]
\end{theorem}

\begin{theorem}[\cite{sauer}] \label{sauer-monoton}
For every $ k \geq 2 $, $ g \geq 3 $,
\[ n(k,g) < n(k,g+1), \]
and, for even $k$, 
\[ n(k,g) \leq n(k+2,g). \]
\end{theorem}

The first inequality of Theorem~\ref{sauer-monoton} is proved by sharpening Theorem~\ref{sachs-monoton}.
The proof of the second inequality takes advantage of the existence of $2$-factors 
for regular graphs of even degree.

To avoid trivialities, henceforth we will
assume that the graphs under consideration have
degree at least 3 and girth at least 5.

\section{Known Cages}
Recall that unless there exists a Moore graph, we know that
$n(k,g)$ is strictly greater than the Moore 
bound.  Thus, in order to prove that a specific graph is a $(k,g)$-cage, 
the non-existence of a smaller $(k,g)$-graph has to be established.
These lower bound proofs are in general very difficult, and
consequently, in addition to the Moore graphs, very few cages are
known.

In this section, we describe all the known cages.
These include three infinite families of geometric graphs,
and a finite number of small examples.
The latter group includes cages of
degree $3$ for girths up to $12$, cages of girth $5$ for degrees up to 
$7$, the $(7,6)$-cage, and the $(4,7)$-cage.

\subsection{Small Examples}
The case of $k=3$ has received the most attention, and
the value of $n(3,g)$ is known for all $g$ up to $12$.  
These values are given in \hyperlink{tableone}{Table 1}.

The $(3,5)$, $(3,6)$, $(3,8)$, and $(3,12)$-cages are Moore graphs.
Showing that the
remaining cases in the table are indeed cages
requires additional arguments:

\begin{quotation}
There is no Moore graph of girth $7$, where the Moore bound is $22$, 
so the lower bound of $n(3,7) \geq 24$ follows immediately.
The proof for girth $10$ was computer assisted \cite{okwong10}, while
the proofs for girth $9$ in \cite{brimcksaa} and girth $11$ in \cite{mckmyr}
involved extensive computer searches.
\end{quotation}

\vspace{5mm}
\hypertarget{tableone}{}
\begin{center}
\begin{tabular}{|l||r|r|r|r|r|r|r|r||} \hline
  $g$ &  5 &  6 &  7 &  8 &  9 & 10 &  11 &  12 \\ \hline
  $n(3,g)$ & \hyperlink{cage35tar}{10} & \hyperlink{cage36tar}{14} &
      \hyperlink{cage37tar}{24} & \hyperlink{cage38tar}{30} &
      \hyperlink{cage39tar}{58} & \hyperlink{cage310tar}{70} &
      \hyperlink{cage311tar}{112} & \hyperlink{cage312tar}{126} \\
  number of cages & 1 & 1 & 1 & 1 & 18 & 3 & 1 & 1 \\ \hline
\end{tabular}

\vspace{3 mm}
\noindent
{\bf Table 1. } Known trivalent cages.
\end{center}

The cages for girth five are known for degrees up to $7$ and are listed
in \hyperlink{tabletwo}{Table 2}. 
The $(3,5)$-cage, the Petersen graph,
and the $(7,5)$-cage, the Hoffman-Singleton
graph, are Moore graphs.
The remaining cases were resolved by a combination of counting arguments
and case analysis \cite{robertson,okwong5,wegner}.

\begin{center}
\hypertarget{tabletwo}{}
\begin{tabular}{|l||r|r|r|r|r|r|r|r||} \hline
 $k$ &  3 &  4 &  5 &  6 &  7 \\  \hline
 $n(k,5)$  & \hyperlink{cage35tar}{10} & \hyperlink{cage45tar}{19} &
       \hyperlink{cage55tar}{30} & \hyperlink{cage65tar}{40} &
       \hyperlink{cage75tar}{50} \\
 number of cages &  1 &  1 &  4 &  1 &  1 \\ \hline
\end{tabular}

\vspace{3 mm}
\noindent
{\bf Table 2. } Known cages of girth $5$.
\end{center}

The case of the $(7,6)$-cage was settled in \cite{okwong6},
and the value of $n(4,7)$ was recently determined in \cite{emmn}.

Next, we provide brief descriptions of the small cages.

\hypertarget{cage35tar}{}
\subsubsection{(3,5)-Cage: Petersen Graph}
The Petersen graph \cite{petersen}
is the $(3,5)$-cage and
has order $10$.
It can be constructed as the
complement of the line graph of $K_5$,
from which it follows that
the automorphism group is isomorphic to
$Sym(5)$.
It is vertex-transitive, edge-transitive,
3-connected, neither planar nor Hamiltonian,
and is the subject of an entire book \cite{petersenbook}.
It is shown in \hyperlink{petefig}{Figure~\ref{petelab}}.

\hypertarget{petefig}{}
\begin{figure}[ht]
\centering
\includegraphics[width=5cm]{pete.png}
\caption{The Petersen graph}
\label{petelab}
\end{figure}

\hypertarget{cage36tar}{}
\subsubsection{(3,6)-Cage:  Heawood Graph}
\label{heawood}
The Heawood graph is the $(3,6)$-cage and
has order $14$.
It is the
point-line incidence graph of the
projective plane of order $2$ (see \ref{projplane}).
It is vertex-transitive, edge-transitive, and the full automorphism
group has order $336$ (and is isomorphic to $PGL(2,7)$).
The usual drawing is
shown in \hyperlink{heawoodfig}{Figure~\ref{heawoodlab}}.

\hypertarget{heawoodfig}{}
\begin{figure}
\centering
\includegraphics[width=5cm]{heawood.png}
\caption{The Heawood graph}
\label{heawoodlab}
\end{figure}

\hypertarget{cage37tar}{}
\subsubsection{(3,7)-Cage:  McGee Graph}
\label{mcgee}
The McGee graph is the $(3,7)$-cage and
has order $24$.
It is the first trivalent cage that is
not a Moore graph.  Its order exceeds
the Moore bound by two.
It is also the smallest of the trivalent cages that is
not vertex-transitive.  There are
two vertex orbits of lengths
$8$ and $16$.  The full automorphism
group has order $32$.
The standard drawing is shown in
\hyperlink{mcgeefig}{Figure~\ref{mcgeelab}}.
In the figure, the vertices
colored red are in one orbit and the
vertices in green in the other.

\hypertarget{mcgeefig}{}
\begin{figure}[ht]
\centering
\includegraphics[width=5cm]{mcgee.png}
\caption{The McGee graph}\label{mcgeefig}
\label{mcgeelab}
\end{figure}

\hypertarget{cage38tar}{}
\subsubsection{(3,8)-Cage: Tutte-Coxeter Graph}
\label{tutte}
The Tutte-Coxeter graph (sometimes called Tutte's cage)
is the $(3,8)$-cage and
has order $30$.
It is the
point-line incidence graph of the
generalized quadrangle of order 2 (see \ref{genquad}).
It is vertex-transitive and
4-arc transitive.  The
full automorphism group has order 1440.
The graph is shown in \hyperlink{tuttefig}{Figure~\ref{tuttelab}}.

\hypertarget{tuttefig}{}
\begin{figure}[ht]
\centering
\includegraphics[width=5cm]{tutte.png}
\caption{The Tutte-Coxeter graph}\label{tuttefig}
\label{tuttelab}
\end{figure}

\hypertarget{cage39tar}{}
\subsubsection{(3,9)-Cages}
\label{cage39}
There are 18 different $(3,9)$-cages, each of order
$58$.
The first of these graphs was discovered by
Biggs and Hoare \cite{biggshoare}.
The list of $18$ graphs was shown to be complete by
Brinkmann, McKay and Saager in 1995 \cite{brimcksaa}.
The orders of the automorphism groups range from 1 to 24.

\hypertarget{cage310tar}{}
\subsubsection{(3,10)-Cages}
\label{cage310}
There are three $(3,10)$-cages of order $70$.
The first of these was discovered
by Balaban \cite{balabanjct}.
The other two were found 
by O'Keefe and Wong \cite{okwong10}.
The completeness of the set was established by Wong \cite{wong310}
and, in another context, by McKay \cite{greechie}.
None of the graphs are vertex-transitive.  The orders
of the automorphism groups are $24$, $80$, and $120$.

\hypertarget{cage311tar}{}
\subsubsection{(3,11)-Cage: Balaban Graph}
\label{cage311}
A $(3,11)$-graph on $112$ vertices was first
constructed by Balaban \cite{balaban} in 1973.
It can be obtained from the $(3,12)$-cage by excision (see \ref{excision}).
The graph was shown to be the unique cage by
McKay, Myrvold and Nadon \cite{mckmyr}.
It is not vertex-transitive, and its automorphism group
has order $64$.

\hypertarget{cage312tar}{}
\subsubsection{(3,12)-Cage: Benson Graph}
\label{benson}
A $(3,12)$-graph on $126$ vertices was first
constructed by Benson \cite{benson} in 1966.
It is the incidence graph of the generalized
hexagon of order 2 (see \ref{genhex}).
The graph is vertex-transitive and edge-transitive.  Its
automorphism group has order $12096$ and is
a ${\Bbb Z}_2$ extension of $PSU(3,3)$.

\hypertarget{cage45tar}{}
\subsubsection{(4,5)-Cage: Robertson Graph}
The Robertson graph is the unique $(4,5)$-cage
of order $19$ (see \cite{robertson}).
It is not vertex-transitive and the full automorphism group
is isomorphic to the dihedral group of order $24$.
It is shown in
\hyperlink{robertsonfig}{Figure~\ref{robertsonlab}},
wherein the three colored vertices on the
right are adjacent to the four vertices on the 12-cycle with the
corresponding color.

\hypertarget{robertsonfig}{}
\begin{figure}[ht]
\centering
\includegraphics[width=6cm]{robertson.png}
\caption{The Robertson graph}\label{robertsonfig}
\label{robertsonlab}
\end{figure}

\hypertarget{cage55tar}{}
\subsubsection{(5,5)-Cages}
The four $(5,5)$-cages have order $30$ \cite{karteszi,drg}.
Their automorphism
groups have orders $20$, $30$, $96$, and $120$.  The first of
these is a subgraph of the Hoffman-Singleton graph (see \ref{hoffsing2}).
The last is known as the Robertson-Wegner graph \cite{wegner}.
It can be constructed as follows.

Begin with a regular dodecahedron, $D$.
The vertices of $D$
determine five (regular) cubes.
Furthermore, each of these
cubes determines two regular tetrahedra. 
The vertices of the Robertson-Wegner
graph are the 20 vertices of $D$, plus one vertex for each of
the 10 tetrahedra.  Each of the tetrahedral vertices is adjacent
to its four determining vertices.  In
addition, two tetrahedral vertices are adjacent if they
are contained in the same cube.

\hypertarget{cage65tar}{}
\subsubsection{(6,5)-Cage}
The $(6,5)$-cage is unique and has order $40$.
It was first presented in \cite{okwong5}
and was proved to be minimal
in \cite{wong}.
It can be constructed by removing the vertices of
a Petersen graph from the Hoffman-Singleton graph (see \ref{hoffsing2}).
It is vertex-transitive with an automorphism group of
order $480$.

\hypertarget{cage75tar}{}
\subsubsection{(7,5)-Cage: Hoffman-Singleton Graph}
\label{hoffsing2}
The Hoffman-Singleton graph is the unique $(7,5)$-cage
\cite{hoffsing}.
The graph was first considered at least as long ago
as 1956 by Mesner \cite{mesner}
(further details can be found in
\cite{jajjaj,shrsan}).
There are several constructions known
(see, for example, \cite{hafner}).

The standard construction, Robertson's
{\em pentagons and pentagrams} \cite{bensonlosey},
begins with
five pentagons $P_i$ and five pentagrams $Q_j$,
$0 \leq i,j \leq 4$, obtained by labeling
the vertices
so that vertex $k$ of $P_i$ is adjacent to vertices $k-1$ and $k+1$
of $P_i$ and vertex $k$ of $Q_j$ is adjacent to vertices
$k-2$ and $k+2$ of $Q_j$ (all subscript arithmetic is done modulo 5).
The graph is completed by joining
vertex $k$ of $P_i$ to vertex $ij+k$ of $Q_j$
(so that each $P_i$ together with each $Q_j$ induce a Petersen graph).

One can obtain the $(6,5)$-cage and one of the $(5,5)$-cages from
this construction.  To get the $(6,5)$-cage, simply delete a
pentagon and the corresponding pentagram.  To obtain a $(5,5)$-cage
delete two of the pentagons and the corresponding pentagrams.

The graph is vertex-transitive and edge-transitive.  Its
full automorphism group has order $252000$ and is isomorphic to
a ${\Bbb Z}_2$ extension of $PSU(3,5)$.

\hypertarget{cage76tar}{}
\subsubsection{(7,6)-Cage}
This case was settled by
O'Keefe and Wong \cite{okwong6},
who showed that $n(7,6) = 90$.
The cage is the incidence graph of an elliptic semiplane
discovered some years earlier by Baker \cite{baker}.
The graph is vertex-transitive and
its full automorphism group has order $15120$.

\hypertarget{cage47tar}{}
\subsubsection{(4,7)-Cage}
Recently, Exoo, McKay, Myrvold and Nadon \cite{emmn} showed that
$n(4,7) = 67$. They exhibited one $(4,7)$-cage on $67$ vertices
whose automorphism group has order 4.
It is unknown whether other $(4,7)$-cages exist.

\subsection{Geometric Graphs}
\label{geomref}
Geometric graphs are based on generalized polygons
whose incidence graphs form three infinite families
of cages (girths 6, 8 and 12).

We begin with the definition of a generalized polygon (or $n$-gon).
Let $P$ (the set of points) 
and $B$ (the set of lines) be disjoint non-empty sets, and let
$I$ (the point-line incidence relation) be a subset of 
$ P \times B $. Let ${\cal I} = (P,B,I)$, and let $G({\cal I})$
be the associated bipartite {\em incidence graph} on $ P \cup B $
with edges joining the points from $P$ to their incident
lines in $B$ ($p \in P$ is adjacent to $\ell \in B$ whenever
$ (p,\ell) \in I $).

The ordered triple $(P,B,I)$ is said to be a {\em generalized 
$n$-gon} subject to the following four regularity conditions:
{\em \begin{enumerate}
\item[GP1:] There exist $s\geq 1$ and $t \geq 1$ such that every line 
is incident to exactly $s+1$ points and every point is incident to
exactly $t+1$ lines.
\item[GP2:] Any two distinct lines intersect in at most one point and 
there is at most one line through any two distinct points.
\item[GP3:] The diameter of the incidence graph $G({\cal I})$ is $n$.
\item[GP4:] The girth of $G({\cal I})$ is $2n$.
\end{enumerate} }

While the trivial case $s=t=1$ leads to two-dimensional polygons,
a well-known result of Feit and Higman \cite{feihig} asserts that if 
both $s$ and $t$ are integers larger than $1$, then $n$ equals
$2,3,4,6$ or $8$; with the parameters $3,4,6$ and $8$ corresponding
to the {\em projective planes}, {\em generalized quadrangles},
{\em generalized hexagons}, and {\em generalized octagons}, 
respectively.
Note that the incidence graphs of generalized
octagons are not regular, and so they cannot be cages.

\hypertarget{projplane}{}
\subsubsection{The Incidence Graphs of Projective Planes}
\label{projplane}
As mentioned above, finite projective planes are generalized 
triangles (or $3$-gons). In this case, $s = t$, and projective planes are 
known to exist whenever the order $s$ is a prime power $q = p^k$.
If $s$ is not a prime power, $s \equiv 1,2 \bmod{4}$, and $s$ is not the
sum of two integer squares, then no plane exists \cite{brurys}.
The first case not covered by the above is the case $n=10$, for
which is has been shown \cite{lam} that no plane exists.
All remaining cases are unsettled.

A finite projective plane of order $q$ has $q^2+q+1$ points 
and $q^2+q+1$ lines, and satisfies the following properties.

{\em
\begin{enumerate}
\item[PP1:] Any two points determine a line.
\item[PP2:] Any two lines determine a point.
\item[PP3:] Every point is incident with $q+1$ lines.
\item[PP4:] Every line is incident with $q+1$ points. 
\end{enumerate}
}

The incidence graph of a projective plane of order 
$q$ is regular of degree $q+1$, 
has $2(q^2+q+1)$ vertices, diameter 3, and girth 6.
Since the Moore bound for degree $q+1$ and
girth $6$ is equal to the orders of these graphs, the incidence
graphs of projective planes are $(q+1,6)$-cages. For example,
the $(3,6)$-cage Heawood graph (see \ref{heawood}) is the
incidence graph of the
plane of order $2$.
The plane is shown in
\hyperlink{fanofig}{Figure~\ref{fanolab}}.

\hypertarget{fanofig}{}
\begin{figure}[ht]
\centering
\includegraphics[width=5cm]{fano.png}
\caption{The projective plane of order 2.}
\label{fanolab}
\end{figure}

\hypertarget{genquad}{}
\subsubsection{The Incidence Graphs of Generalized Quadrangles}
\label{genquad}
A generalized quadrangle is an incidence structure
with $s+1$ points
on each line, $t+1$ lines through each point.
It is said to have order $(s,t)$. A generalized quadrangle
of order $(s,t)$ has $(s+1)(st+1)$ points and $(t+1)(st+1)$ lines,
and has the following properties.

{\em 
\begin{enumerate}
\item[GQ1:] Any two points lie on at most one line.
\item[GQ2:] Any two lines intersect in at most one point.
\item[GQ3:] Every line is incident with $s+1$ points.
\item[GQ4:] Every point is incident with $t+1$ lines.
\item[GQ5:] For any point $p \in P$ and line $\ell \in B$, 
where $(p,\ell) \notin I$, there is exactly one line incident 
with $p$ and intersecting $\ell$. 
\end{enumerate}
}

The incidence graph of a generalized quadrangle of order $(q,q)$
has $2(q+1)(q^2+1)$ vertices and is regular of degree $q+1$, 
diameter $4$, and girth $8$. The orders of these
graphs match the Moore bound for degree $q+1$ and girth $8$, and
are therefore cages.
Graphs with these parameters are known to exist whenever $q$ is a 
prime power.
For example,
the $(3,8)$-cage Tutte-Coxeter graph (see \ref{tutte})
is the incidence graph 
of the generalized quadrangle of order $(2,2)$ shown in 
\hyperlink{gq2fig}{Figure~\ref{quadlab}}.
The $15$ lines of the quadrangle are represented
by the five sides of the pentagon, the five diagonals, and the five
partial circles.

\hypertarget{gq2fig}{}
\begin{figure}[ht]
\centering
\includegraphics[width=5cm]{quad.png}
\caption{The generalized quadrangle of order (2,2).}
\label{quadlab}
\end{figure}

\hypertarget{genhex}{}
\subsubsection{The Incidence Graphs of Generalized Hexagons}
\label{genhex}
Generalized hexagons satisfy the following conditions.

{\em
\begin{enumerate}
\item[GH1:] Any two points lie on at most one line.
\item[GH2:] Any two lines intersect in at most one point.
\item[GH3:] Every line is incident with $s+1$ points.
\item[GH4:] Every point is incident with $t+1$ lines.
\item[GH5:] For any point $p \in P$ and line $\ell \in B$, where 
$(p,\ell) \notin I$, there is a unique shortest path from 
$p$ to $\ell$ of length 3 or 5.
\end{enumerate}
}

Once again, the incidence graph of a generalized hexagon of order 
$(q,q)$ is regular of degree $q+1$, diameter $6$, and girth $12$. 
The order of every such graph matches the Moore bound, which in
this case is $2(q^3 + 1)(q^2 + q + 1)$.
Graphs with these parameters are known to exist whenever $q$ is a 
prime power. The $(3,12)$-cage Benson graph (see \ref{benson})
is the incidence graph of the generalized hexagon of order $(2,2)$.

\section{Lower Bounds}

Outside of the cases where Theorem~\ref{moorebound} asserts the existence of
a Moore graph, the obvious lower bound for the order of a $(k,g)$-cage
is the value of the Moore bound plus one, $M(k,g)+1$, when $k$ is even, 
and the value of the Moore bound plus two, $M(k,g)+2$, when $k$ is odd. 

These improved lower bounds do not differ significantly from the Moore bound, $M(k,g)$.
However the Moore bound values are widely believed to be
well below the actual orders $n(k,g)$ of the $(k,g)$-cages.
An inspection of
the lists of the smallest known $(k,g)$-graphs included in
Section~\ref{upper-bounds}
suggests a significant gap between the orders of the best known graphs and the
corresponding
Moore bounds. The difference $n(k,g) - M(k,g)$
is a closely studied quantity,
usually denoted by $\epsilon(k,g)$, and given the name {\em excess}. Despite any evidence
that one may find in the tables, the order of magnitude
of the excess $\epsilon(k,g)$ is an open problem.
While the best general lower bounds (listed in the following paragraphs) add at most a
very small constant to the Moore bound, computational evidence suggests the existence
of parameters for which the excess might in fact be significantly larger than the
Moore bound.

The only theoretical lower bound
that provides at least some evidence as to the nature of the growth
of the excess is due to Biggs and deals exclusively with vertex-transitive graphs.
\begin{theorem}[\cite{big82}] \label{biggsvt}
For each odd integer $ k \geq 3 $ there is an infinite sequence of values
of $g$ such that the excess $e$ of any vertex-transitive graph with
valency $k$ and girth $g$ satisfies $e > g/k$.
\end{theorem}
As the orders of the smallest vertex-transitive $(k,g)$-graphs often significantly differ
from the orders of the corresponding $(k,g)$-cages
(as evidenced in \hyperlink{vttable}{Table 7}),
the applicability of the above result with regard to general $(k,g)$-cages remains unclear.
In the next paragraphs, we list all the known lower bounds on $n(k,g)$.

In \cite{brown}, Brown showed that $n(k,5)$ is never equal to $M(k,5)+1$.
This was further improved by Kov\' acs \cite{kovacs}, who showed that 
$n(k,5)$ is not equal to $M(k,5)+2$ when $k$ is odd and cannot be written
in the form $ \ell^2 + \ell -1 $, for $\ell$ an integer. Eroh and Schwenk
\cite{erosch}
also showed that $n(k,5)$ is not equal to $M(k,5)+2$ for $5 \le k \le 11$.
For girth $7$, Eroh and Schwenk \cite{erosch} showed the non-existence of 
$k$-regular graphs of girth $7$ and order $M(k,7)+1$, and finally Bannai and 
Ito \cite{Ban&Ito} showed the non-existence of $k$-regular graphs of odd girth $g \geq 5$ and
order $M(k,g)+1$ for all degrees $k \geq 3$.
Note that in this case,
the McGee graph \ref{mcgee} achieves the lower bound $M(3,7)+2$, hence is a 
cage. The only other known cage for girth $7$ is the $(4,7)$-cage \cite{emmn} 
of order $67=M(4,7)+14$. 

All cages of even girth have been conjectured to be bipartite by Wong in 
\cite{wongsurvey}.
If the conjecture were true,
$n(k,g) > M(k,g) + 1$ would automatically follow for all $ k \geq 3 $ and even $ g \geq 4 $
for which there does not exist a Moore graph. The following result of Biggs and Ito proves Wong's
conjecture under the following very special circumstances:
\begin{theorem}[\cite{Big&Ito}]
Let $G$ be a $(k,g)$-cage of girth $g = 2m \geq 6$ and excess $\epsilon$. 
If $\epsilon \leq k-2$, then $G$ is bipartite and its diameter is $m + 1$.
\end{theorem}
Consequently, $n(k,g) \geq M(k,g) + 2$ for all $ k \geq 3 $ and even $ g \geq 6 $
for which there does not exist a Moore graph. 
In the very same paper the authors further strengthen this result as follows:
\begin{theorem}[\cite{Big&Ito}]
Let $G$ be a a $(k,g)$-cage of girth $g = 2m \geq 6$ and excess $2$.
Then $g=6$, $G$ is a double-cover of the incidence graph of a symmetric 
$(v,k,2)$-design $D(k,2)$, and $k$ is not congruent to $5$ or $7 \pmod{8}$.
\end{theorem}
In all other cases, $n(k,g) \geq M(k,g)+3 $. The symmetric design $D(k,2)$ is also
called a biplane. The authors observe in their
abstract ``it is a remarkable fact that we get a double-cover of $D(k,2)$ in the 
case when $\epsilon=2$, whereas we get the incidence graph of a projective plane
in the case $\epsilon=0$ and $g=6$."

The cases  $n(5,5)$, $n(6,5)$, $n(7,6)$, and $n(3,10)$ 
were resolved by a combination of counting arguments and case analysis 
\cite{robertson,okwong5,okwong6,okwong10,wegner}.

All the remaining improvements on the lower bounds for cages are based 
on computer searches (see \ref{compref}).
There are three cases where extensive 
computer searches produced the correct lower bound (and the cages are known).
Namely, the cases $n(3,9)$, $n(3,11)$, and $n(4,7)$, \cite{brimcksaa}, 
\cite{mckmyr}, and \cite{emmn}, respectively. In the case $n(3,13)$, the 
lower bound was improved to $202 = M(3,13)+12$ \cite{mckmyr}, and in the 
case $n(3,14)$ the lower bound was improved to $258 = M(3,14)+4$ \cite{mckmyr}.

\section{Upper Bounds}\label{upper-bounds}
In the preceding sections, we have listed and described all the currently known 
cages; graphs whose orders $n(k,g)$ are provably the smallest, and as 
such, will permanently stay on the list.

In what follows, we list graphs whose orders, denoted by $rec(k,g)$,
are the smallest currently known. Although some of these graphs 
may actually be cages, the majority will most likely be eventually replaced
by smaller graphs. 

We adopt a somewhat arbitrary division of the current record holders 
into two groups:
\begin{description}
\item{\em General constructions} --  constructions that produce graphs
with arbitrarily large values of girth or degree (Section~\ref{gencon}).
\item{\em Individual constructions} -- constructions that work for specific 
values of girth and degree, and may have been introduced for other purposes, 
or have been found by the use of computers (Section~\ref{indcon}).
\end{description}

In the next section, we present the general constructions that have 
produced the best known asymptotic bounds on $n(k,g)$. These are 
followed by constructions that are useful
for only a limited number of specific values of $n(k,g)$.

\subsection{General Constructions} \label{gencon}

\subsubsection{Constructions for Large Girth}
In this section we describe constructions for regular graphs
with arbitrarily large girth.  Included are the construction
of Sachs \cite{sachs}, the trivalent sextet, hexagon
and triplet graphs \cite{sextet,hexagon},
as well as the higher degree constructions
of Lubotzky, Phillips and Sarnak \cite{lubphisar},
and Lazebnik, Ustimenko and Woldar \cite{lazustwol}.
We also discuss the techniques of Chandran \cite{chandran}
and of Bray, Parker and Rowley \cite{brayetal}.

Biggs observes in \cite{biggssurvey} that the Moore bound implies
that minimal $k$-regular graphs 
of girth $g$ have approximately $ (k-1)^{g/2} $ vertices. 
Thus, when considering infinite families of $k$-regular graphs 
$\{ G_i \}$ of increasing girth $g_i$,
we compare their orders $v_i$ to the Moore bound.
\hypertarget{biggsfamily}{}
We say that $ \{ G_i \} $ is 
a {\em family with large girth} if there exists $\gamma > 0$ such that
\[ g_i \geq \gamma \log_{k-1}(v_i) . \]
It follows from the Moore bound that $\gamma$ is at most $2$, but there
are no known families with $\gamma$ close to $2$. 
The results of Erd\H{o}s, Sachs \cite{erdossachs}
and Sauer \cite{sauer} showed the existence of infinite families with $\gamma = 1 $.
The first explicit constructions go back to Margulis \cite{margulis} who
achieved $ \gamma = \frac{4}{9} (\approx 0.44) $ for some infinite families 
with arbitrary large degree and $ \gamma \approx 0.83 $ for degree $4$.
These were followed by the results of Imrich \cite{imrich}, who produced
infinite families of large degree with $ \gamma \approx 0.48 $ and a family
of trivalent graphs with $ \gamma \approx 0.96 $. 
The (trivalent) \hyperlink{sextar}{\em sextet graphs} 
of Biggs and Hoare were shown to satisfy $ \gamma \geq 4/3 $ by 
Weiss \cite{weiss}, and the \hyperlink{lpstar}{\em Ramanujan graphs} of Lubotzky,
Phillips and Sarnak \cite{lubphisar} were shown to satisfy 
$ \gamma \geq 4/3 $ (with arbitrary large degree) by Biggs and Boshier
\cite{big&bos}. The (current) best results (for arbitrary large degree)
are due to Lazebnik, Ustimenko and Woldar \cite{lazustwol} who have 
constructed infinite families \hyperlink{luwtar}{$CD(n,q)$}
with $ \gamma \geq 4/3 \log_q(q-1) $, 
$ q $ a power of a prime.

\Constr{trunc}{Sachs}
\label{sachs-trunc}

\noindent
A truncation of a map is a well-known construction from 
topological graph theory in which the vertices of the original map are 
replaced by cycles attached to the dangling edges of the removed vertices. 
The original construction of Sachs from \cite{sachs} is a special case of
a truncation construction.
We present a slight generalization of his construction. 

Let $G$ be a finite $k$-regular graph, and let $D(G)$ denote the set of 
{\em darts} of $G$ obtained by associating each edge of 
$G$ with two opposing directed edges.
A {\em vertex-neighborhood labeling} of $G$ is a function $\rho$ from the 
set $D(G)$ into the set $\{ 1,2,\ldots,k \}$ that maps the
darts emanating from a vertex $v \in V(G)$ bijectively onto $ \{ 1,2,
\ldots, k \}$.
Let $H$ be a graph of order $k$, $V(H)=\{u_1,u_2,\ldots,u_k \}$.
The {\em generalized truncation of a } $k${-regular graph} $G$ 
{\em with a vertex-neighborhood labeling} $\rho$ {\em by the graph} $H$ 
(of order $k$)
is the graph $T(G,\rho; H)$ obtained from $G$ by replacing the vertices
of $G$ by copies of $H$ as follows: each vertex $v$ of 
$G$ is replaced by the graph $H$ attached to the dangling darts 
originally emanating from $v$ according to the rule that $u_i$ is attached
to the dart labeled by $i$.
\hyperlink{zigfig}{See Figure 8.}

\hypertarget{zigfig}{}
\begin{figure}[ht]
\centering
\includegraphics[width=6cm]{zig.png}
\caption{A generalized truncation of $K_6$ by $C_5$.}
\label{ziglab}
\end{figure}

The importance of the generalized truncation for the construction of 
$(k,g)$-graphs becomes clear from the following theorem. 

\begin{theorem}[\cite{bobjaj&pis}] \label{trunc}
Let $G$ be a finite $(k,g)$-graph with a vertex-neighborhood labeling
$\rho$, and let $H$ be a $(k',g')$-graph of order $k$.
The generalized truncation graph $T(G,\rho;H)$ is a 
$(k'+1)$-regular graph of girth not smaller than $\min \{ 2g,g' \}$,
and if $g' \leq 2g $, then $g'$ is the exact girth of $T(G,\rho;H)$.
\end{theorem}

The proof of this theorem relies on a careful inspection of the effects 
of the truncation on the original cycles of $G$. 

As mentioned in our introduction, the first proof of the existence of graphs for
any pair of parameters $k$ and $g$ can be found in  \cite{sachs}. The 
construction used in this proof is recursive and based on generalized truncation. 
It proceeds as follows.

\begin{theorem}[\cite{sachs}]
For every pair of parameters $k \geq 2$ and $g \geq 3$, there exists a finite
$k$-regular graph of girth $g$.
\end{theorem}
{\bf Proof.} We proceed by induction on $k$. If $k=2$, the $g$-cycle 
${\cal C}_g$ is a $(2,g)$-cage for all $ g \geq 3$.

For the induction step, assume the existence of a $(k,g)$-graph $H$ for some
$ k \geq 2 $ and $g \geq 3$ of order $n$. 
Let $G$ be an $n$-regular graph
of girth at least $\lceil \frac{g}{2} \rceil$ guaranteed by the construction 
from Theorem~\ref{biggs-at-least}, and let $\rho$ be any vertex-neighborhood labeling 
of $G$. Theorem~\ref{trunc} asserts that the truncated graph 
$T(G,\rho;H)$ is a $(k+1)$-regular graph of girth $g$. \hfill $\square$
\medskip

The construction of Sachs has more recently
reappeared as the {\em zig-zag construction},
which has successfully been used in the context of expander graphs
\cite{reivadwig}.

\Constr{sextar}{Sextet Graphs}
\label{sextetref}

\noindent
Sextet graphs are trivalent graphs introduced by Biggs and Hoare
in \cite{sextet}.
Let $q$ be an odd prime power.
A {\em duet}, $ab$,
is any 
unordered pair of elements from
${\Bbb F}_q \cup \{ \infty \} $,
the points of the projective line $PG(1,q)$.
A {\em quartet} is an unordered pair of duets, $ab$ and 
$cd$, satisfying the equality
$$
\frac{(a-c)(b-d)}{(a-d)(b-c)} = -1.
$$
If one of the vertices is infinity, then
$\{\infty,b\;|\;c,d\}$ is a quartet if
$$
\frac{(b-d)}{(b-c)} = -1.
$$

A {\em sextet} is an unordered triple of duets such that 
every pair of duets from the triple forms a quartet.

Assume that $q \equiv 1\bmod{8}$.
Any quartet uniquely determines a sextet.
The group $PGL(2,q)$ of projective linear transformations of
$PG(1,q)$ preserves and acts transitively on quartets.
In addition, given a quartet $\{a, b\;|\; c, d\}$
there is a unique involution in $PGL(2,q)$ that interchanges
$a$ with $c$ and $b$ with $d$, and whose fixed points constitute
a duet $ef$ such that $\{a, b\;|\; c, d\;|\;e, f\}$ is a
sextet.

Next we define adjacency on the sextets.
A sextet $s = \{a, b\;|\; c, d\;|\;e, f\}$ is
adjacent to three other sextets, each having
a different duet in common with $s$.
For example, $s$ is adjacent to
$\{a, b\;|\; c', d'\;|\;e', f'\}$
where the duet $c'd'$ is the pair of points
fixed by the involution mapping $c$ to $e$ and
$d$ to $f$, and
the duet $e'f'$ is the pair of points
fixed by the involution mapping $c$ to $f$ and
$d$ to $e$. 

It can be shown that
there exist exactly $q(q^2-1)/24$ 
sextets.
The set of all sextets under the above
adjacency relation defines the
trivalent graph $\Sigma(q)$.
In general, $\Sigma(q)$ is not connected. 

If $p$ is an odd prime, the {\em sextet graph} $S(p)$ is 
any connected component of $\Sigma(p)$, for $ p \equiv 1
\bmod{8}$, and its order is
$\frac{1}{48}p(p^2-1)$.

The graph \hyperlink{rec322}{$S(73)$}
is the smallest known
trivalent graph of girth $22$.

\Constr{hextar}{Hexagons}
\label{hexgraphref}

Hexagon graphs are trivalent graphs introduced by Hoare in \cite{hexagon}.
Let $p$ be a prime, $p > 3$, and let $q = p$ if $p \equiv 1 \bmod{4}$ and
$q = p^2$ otherwise.
Consider the complete graph
$K_{q+1}$ with vertices labeled by elements of ${\Bbb F}_q \cup \{\infty\}$,
the points of the projective line $PG(1,q)$.
The concepts of duet, quartet, and sextet are defined as \hyperlink{sextar}{above}.

For any $6$-cycle $C$ in $K_{q+1}$, define a {\em short diagonal} to be
a pair of vertices whose distance in $C$ is $2$, and a {\em long
diagonal} to be
a pair of vertices whose distance in $C$ is $3$.
A $6$-cycle $C$ in $K_{q+1}$ is a {\em hexagon}
if any four of its vertices,
$v_1, v_2, v_3, v_4$, such that $v_1, v_2$ form a short
diagonal and  $v_3, v_4$ form a long diagonal determine
a quartet $\{v_1,v_2\;|\;v_3,v_4\}$.

This set of hexagons is the vertex set of a trivalent
graph denoted $H(q)$, wherein adjacency is defined
as follows:

\begin{quotation}
Let $H = v_1, v_2, v_3, v_4, v_5, v_6$ be a hexagon.
Each of its three long diagonals determines one
neighbor of $H$.  For example, the long
diagonal $v_1, v_4$ together with the
short diagonals $v_2, v_6$ and $v_3, v_5$ determines
unique sextets
$\{v_1, v_4\;|\; v_2, v_6\;|\;v_7, v_8\}$ and
$\{v_1, v_4\;|\; v_3, v_5\;|\;v_9, v_{10}\}$, which
in turn determine the adjacent hexagon
$v_1, v_7, v_9, v_4, v_8, v_{10}$.
\end{quotation}

The graph \hyperlink{rec319}{$H(47)$} is the smallest known
trivalent graph of girth $19$.

\Constr{triptar}{Triplets}

\noindent
Let $p$ be an odd prime.
The vertex set of the trivalent {\em triplet graph} $T(p)$
is the set of all $3$-subsets of the points of $PG(1,p)$.
Two $3$-subsets $\{a,b,c\}$ and $\{a,b,d\}$ are
adjacent if and only if $\{a,b\;|\;c,d\}$ is a quartet.

It was shown in \cite{hexagon} that if $p \equiv 1 \bmod{4}$ then
$T(p)$ has two connected components of size $p(p^2-1)/12$, and
if $p \equiv 3 \bmod{4}$ then $T(p)$ is connected of order
$p(p^2-1)/6$.

The girth of $T(p)$ is greater than $log_{\phi}(p)$, where
$\phi$ is the golden ratio $(1 + \sqrt(5))/2$.
Finally,
it may be interesting to note that
the connected components of $T(5)$ are Petersen graphs.

\Constr{lpstar}{Lubotzky, Phillips, Sarnak}

\noindent
The graphs obtained from this construction are Cayley graphs
(see \ref{cayref}) of projective linear groups.
They belong to the family of {\em Ramanujan graphs}, which are
$k$-regular graphs whose second largest (in absolute value)
eigenvalue $\lambda_2$ satisfies the inequality 
$\lambda_2 \leq 2 \sqrt{k-1} $. 

Let $p$ and $q$ be distinct primes such
that $p,q \equiv 1 \bmod{4} $,
and let $i$ be an integer satisfying $ i^2 \equiv -1 \bmod{q} $. Then there 
are $8(p+1)$ solutions $ \alpha=(a_0,a_1,a_2,a_3) $ satisfying 
$ a_0^2 + a_1^2 + a_2^2 + a_3^2 = p $. Exactly $p+1$ of these $4$-tuples
$\alpha$ are
such that their first coordinate $a_0$ is positive and odd and the rest of the 
coordinates $a_1, a_2, a_3 $ are all even. 
Associate each such $\alpha$ with the matrix $ \tilde{\alpha} \in PGL(2,q) $
defined by 
\[
\tilde{\alpha} = \left( \begin{array}{cc} 
a_0 + i a_1 & a_2 + ia_3 \\
-a_2 + ia_3 & a_0 - ia_1 \\
\end{array} \right).
\]
Let $\Lambda$ denote the set of the $p+1$ matrices obtained in this way.

The graphs $X^{p,q}$ are \hyperlink{cayref}{Cayley graphs} of degree
$p+1$ defined in two different ways depending 
on the sign of the Legendre symbol $\left (\frac{p}{q} \right)$:

\[
X^{p,q} =
\left\{ \begin{array}{ll}
 C(PSL(2,q),\Lambda) & \mbox{ if } \left( \frac{p}{q} \right) = 1, \\
 C(PGL(2,q),\Lambda) & \mbox{ if } \left( \frac{p}{q} \right) = -1. \\
\end{array}\right.
\]

The orders of the graphs are the orders of the linear groups, which are
$\frac{q(q^2-1)}{2}$ and $q(q^2-1)$, respectively.
The latter graph is bipartite.

In order to state their result precisely, we need their
concept of a {\it good integer}, which is one that cannot
be expressed in the form
$4^{\alpha}(8\beta +7)$ for nonnegative integers 
$\alpha, \beta$.

\begin{theorem}[\cite{lubphisar}]
\[
g(X^{p,q}) = \left\{ 
\begin{array}{ll}
2\lceil 2\log _p{q}  \rceil & \mbox{ if } p^{\lceil 2\log_p{q} \rceil} - q^2 \mbox{ is good,} \\
2\lceil 2\log_p{q} + \log _p{2} \rceil  & \mbox{ otherwise.} 
\end{array}
\right.
\]
\end{theorem}

Hence, the girths of the resulting graphs are asymptotically
$ \frac{4}{3} \log_p(n)$, where $n$ is the order of the
graph \cite{lubphisar}.

\Constr{luwtar}{Lazebnik, Ustimenko, Woldar}

Let $q$ be a prime power, and let $P$ (points) and $L$ (lines) be two 
copies of the set of infinite sequences of elements from the
finite field ${\Bbb F}_q$. We adopt the convention that the points in $P$
will be denoted by 
\[ (p) = \{ p_1, p_{1,1}, p_{1,2}, p_{2,1}, p_{2,2}, p_{2,2}', p_{2,3}, \ldots,
p_{i,i}, p_{i,i}', p_{i,i+1}, p_{i+1,i}, \ldots \}, \]
and the lines in $L$ will be denoted by 
\[ [l] = \{ l_1, l_{1,1}, l_{1,2}, l_{2,1}, l_{2,2}, l_{2,2}', l_{2,3}, \ldots,
l_{i,i}, l_{i,i}', l_{i,i+1}, l_{i+1,i}, \ldots \}. \]

A point $(p)$ is incident to the line $[l]$ subject to the following:
\[
\begin{array}{lclcl} \label{D(n,q)}
l_{1,1} & - & p_{1,1} & = & l_1 p_1 \\
l_{1,2} & - & p_{1,2} & = & l_{1,1} p_1 \\
l_{2,1} & - & p_{2,1} & = & l_1 p_{1,1} \\
l_{i,i} & - & p_{i,i} & = & l_1 p_{i-1,i} \\
l_{i,i}' & - & p_{i,i}' & = & l_{i,i-1} p_1 \\
l_{i,i+1} & - & p_{i,i+1} & = & l_{i,i} p_1 \\
l_{i+1,i} & - & p_{i+1,i} & = & l_1 p_{i,i}',
\end{array}
\]

\noindent
with the last four equations defined for $i \geq 2 $.

For each positive $n \geq 2 $, the first $n-1$ equations
define an incidence relation on $P_n, L_n $, two copies of $({\Bbb F}_q)^n$, 
thought of as the projections of the infinite sequences from $P$ and $L$ 
onto their $n$ first coordinates. 
The graph $D(n,q)$ is the bipartite incidence graph 
corresponding to the incidence structure induced on $P_n$ and $L_n$.

For all $n>1$, the graphs $D(n,q)$ are $q$-regular graphs of order $2q^n$ 
and girth $g \geq n+4$ when $n$ is even, and girth $g \geq n+5$ when $n$ is odd.
The automorphism groups of these graphs are transitive on points,
lines, and edges. 
Moreover, for $n \geq 6$, the graphs $D(n,q)$ are disconnected with 
all of their connectivity components $CD(n,q)$ mutually isomorphic.
Hence, for $n \geq 6 $ and $ q $ a prime power, the graphs $CD(n,q)$ are
bipartite, connected, $q$-regular graphs of order
$ \leq 2q^{n- \lfloor \frac{n+2}{4} \rfloor +1} $,
girth $ g \geq n+4 $, and have point, line, and edge-transitive automorphism
groups \cite{lazustwol,lazustwol2}.
The smallest non-trivial graph in their family is $CD(2,3)$, also known as
the Pappus graph, shown in
\hyperlink{pappus}{Figure~\ref{pappus}}.

\hypertarget{pappus}{}
\begin{figure}[ht]
\centering
\includegraphics[width=5cm]{pappus.png}
\caption{The Pappus graph}\label{pappusfig}
\label{pappus}
\end{figure}


Using this construction, in conjunction with the constructions
of \hyperlink{lpstar}{Lubotzky, Phillips, and Sarnak} \cite{lubphisar},
and of
F\" uredi, Lazebnik, Seress, Ustimenko, and Woldar \cite{furser},
one obtains the following bound.

\begin{theorem}[\cite{lazustwol2}]
Let $k \ge 2$ and $g \ge 5$ be 
integers, and let
$q$ denote the smallest odd prime power 
for which $k\le q$.
Then
$$n(k,g)\le 2kq^{\frac{3}{4}g - a}, \eqno (2)$$
 where $a = 4$, $11/4$, $7/2$, $13/4$ for
$g\equiv  0, 1, 2, 3 \bmod{4}$, respectively.
\end{theorem}

\Constr{chandran}{Chandran}

\noindent
Chandran \cite{chandran} devised a simple algorithm 
that constructs a graph of order $n$ with
degree set a subset of $\{k-1, k, k+1\}$.
He begins with either a matching or a Hamiltonian
cycle, and adds edges one at a time based on distance and degree.
He is able to show that the resulting graph has $log(n)$ girth.

\Constr{bprtar}{Bray, Parker, Rowley}

\noindent
Historically,
highly symmetric graphs (see \ref{symmref})
repeatedly proved useful in
constructions of relatively small (trivalent) graphs of specific
girth.  A number of the early best constructions were Cayley graphs
(see \ref{cayref}).  The symmetry of Cayley graphs makes the girth
computations more efficient than for asymmetric graphs of the same
order.  When working with Cayley graphs, it is important
to choose groups in which the group operation can be computed
quickly.  Hence, groups which can be represented as groups of small
matrices are a natural choice.  Several of the early records constructed
in this way can be found in \cite{conder}.

Improvements on some of the records obtained using Cayley graphs
were made by modifying Cayley graphs.
Bray, Parker and Rowley \cite{brayetal}
constructed a number of current record holders for degree three
by factoring out the $3$-cycles in trivalent Cayley graphs.
Their construction starts with a trivalent Cayley graph,
$C(G,X)$, subject to the condition that the generating set $X$ contains 
an involution, $\alpha$, and two mutually inverse elements of order $3$, 
$\delta, \delta^{-1}$, and that
the Cayley graph has no cycles of length $4$.
The graph $B(G,X)$ is
then defined as follows: the vertex set ${\cal T}$ of $B(G,X)$ is the 
set of triangles of $C(G,X)$ with triangle $T_i$ adjacent to
triangle $T_j$ in $B(G,X)$
if at least one of the vertices of $T_i$ is adjacent in $C(G,X)$ 
to at least one of the vertices of $T_j$ via an edge labeled by the 
involution $\alpha$.

\subsubsection{Constructions for Girth 5}

Next we present a series of constructions that produce
families of fixed girth 5.
We attempt to provide a list that is as complete as
possible, including older constructions that may still
prove useful, and newer constructions whose efficiency is
sometimes hard to compare.

The constructions below produce graphs whose orders
are approximately
twice the Moore bound, which is $k^2+1$
for degree $k$ and girth $5$.

\Constr{brotar}{Brown}

Brown \cite{brown} constructed a family of graphs of
girth 5 based on his
\hyperlink{bro2tar}{construction for girth 6} \cite{brownham}.

He begins with a set of points
$P = \{ p_0 , \dots , p_q \}$ and
a set of lines $L = \{ \ell_0 , \dots , \ell_q \}$,
such that $p_0$ is incident with all the lines in $L$ and
$\ell_0$ is incident with all the points in $P$, and removes
it from $PG(2,q)$.
The incidence graph of the resulting geometry is
a $q$-regular graph of girth $6$ and order $2q^2$.
He then adds $q$-cycles to the neighborhoods of
the deleted vertices $\{ p_1 , \dots , p_q \}$
and $\{ \ell_1 , \dots , \ell_q \}$.
The resulting graph has degree $q+2$, girth $5$, and
order $2q^2$.

\Constr{wegtar}{Wegner}

Wegner \cite{wegner} constructed a family of graphs of
prime degree $k$, girth 5, and order $2k^2 - 2k$.

Let $p \ge 5$ be a prime.
The graph is constructed by connecting the vertices
of a $p^2$-cycle $A$ to an independent set $B$ of size
$p(p-2)$.
Denote the vertices of $A$ by
$a_0 , \dots , a_{p^2 - 1}$, with each $a_i$ adjacent
to $a_{i+1}$;
denote the vertices of $B$ by $b_{s,t}$, for
$0 \leq s \leq p-3$ and $0 \leq t \leq p$.
The adjacencies between the vertices of the cycle and the
independent set are defined as follows.
For each $a_k$, write $k$ as $ip + j$, where $0 \leq i,j < p$, and
make $a_{ip+j}$ adjacent to $b_{r,ir+j}$, for $0 \leq r \leq p-3$.

The smallest of Wegner's graphs is of degree $k=5$ and has order $40$.
Note that the $(5,5)$-cage has order $30$.

\Constr{partar}{Parsons}

Parsons used finite projective planes to construct infinite families 
of regular graphs of girth five \cite{parsons}.
The best of these has degree $k=(q+1)/2$ (for prime power $q$)
and has order $2k^2 - 3k + 1$.

Recall that the projective plane $PG(2,q)$ can
be constructed from the one and two-dimensional
subspaces of a 3-dimensional vector space over the
field ${\Bbb F}_q$.  Parsons defines a graph
$G(q)$ on the points of $PG(2,q)$, with two points adjacent 
if they are distinct and their dot product (as vectors in ${\Bbb F}_q^3$)
is zero.
The graphs Parsons constructs are induced subgraphs of $G(q)$.

To specify the graphs, he partitions the vertex set
into three subsets, $R$, $S$, and $T$, as follows.
Let $R$ be the set of self-orthogonal points (as vectors in ${\Bbb F}_q^3$), 
$S$ be the set of points adjacent to some point in $R$, and $T$ be all
the remaining points.  He proves that if $q \equiv 3 \bmod{4}$,
the subgraph induced by $S$ has order $q(q+1)/2$ and
is regular of degree $(q-1)/2$ and has girth 5, and if $q \equiv 1 \bmod{4}$,
the subgraph induced by $T$ has order $q(q-1)/2$ and is regular of 
degree $(q+1)/2$ and has girth 5.

When $q=5$, Parsons construction produces the Petersen graph, and when 
$q=7$, it produces the Coxeter graph. 

\Constr{okwtar}{O'Keefe and Wong} 

A construction based on
Latin squares was described by O'Keefe and Wong \cite{okwongg5}.
It can be viewed as a generalization of Robertson's
pentagon-pentagram construction of the Hoffman-Singleton
graph \ref{hoffsing2}.
Their construction generates the strongest results
when the degree $k=q+2$, for a prime power $q$, in
which case
the order of their graphs is $2k^2 - 8k + 8$.
This is the case described below.
In the general case, when $3 \leq k \leq q+1$, the
orders of the graphs are $2q(k-2)$.

Let $q = p^r$ be a prime power.
O'Keefe and Wong construct a set of $q$
mutually orthogonal squares with entries from ${\Bbb F}_q$,
with the last $q-1$ of these comprising a complete set of mutually
orthogonal Latin squares \cite{vanwil}.
The Latin squares are constructed as follows.
Let $a$ be a primitive element of ${\Bbb F}_q$, and
order the field elements as powers of $a$:
$b_0 = 0, b_1 = 1, b_2 = a , \dots , b_{q-1} = a^{q-2}$.
Then the squares $L_i$,
$1 \leq i \leq q-1$, are defined by
setting the $(i,j)$ entry of $L_k$ to $b_k(b_i + b_j)$.
Also let $L_0$ be the square whose
$(i,j)$ entry is $j$.  Note that $L_0$ is not a Latin square,
but is orthogonal to each of the Latin squares $L_1, \dots, L_{q-1}$.

Next define a graph on the two sets of doubly indexed vertices,
$X = \{x_{i,j}\}$ and $Y = \{y_{i,j}\}$, $0 \leq i,j \leq q-1$.
Let the $x_{k,j}$ be adjacent to $y_{i,t}$,
whenever $t$ is the $(i,j)$ entry of $L_k$.
Since the squares are orthogonal,
the resulting graph is a $q$-regular bipartite graph of girth $6$.

To increase the degree to $q+2$,
the edges of a 2-regular graph are added in such a way that
no cycles of length 3 or 4 are introduced.
Define $X_i = \{x_{i,0} , \dots , x_{i,q-1} \}$
and $Y_i = \{y_{i,0} , \dots , y_{i,q-1} \}$.
Suppose $q = p^r$ and $p \geq 5$.
Add edges between $x_{i,j}$ and $x_{i,j+a}$, and
between $y_{i,j}$ and $y_{i,j+a^2}$, for $0 \leq i,j < q$.
Note that the 2-regular graph induced on $X_i$ (and $Y_i$)
consists of disjoint $p$-cycles.

In cases $p=2$ and $p=3$ the construction is similar in
spirit, but is more intricate, and results in the addition
of $8$-cycles and $9$-cycles, respectively.

When $q=5$, this construction yields the Hoffman-Singleton
graph.

\Constr{wangtar}{Wang}

Wang \cite{wang} constructed a family of $(k,5)$-graphs
for $k = 2^s + 1$.  This construction uses a complete
set of Latin squares of order $2^s$, $L_1, \dots , L_{k-2}$,
together with the square $L_0 = [a_{i,j}]$,
with $a_{i,j} = i$, for $0 \leq j \leq k-2$.

The construction is based on a tree obtained by taking an
edge $uv$, and joining $k-1$ leaves to each of $u$ and
$v$.  The resulting tree has diameter $3$ and $2k$ vertices.

Begin with $2^{s-1}$ copies of the above tree, $T_0, \dots , T_{2^{s-1}-1}$,
and label the two sets of leaves in $T_i$ by $\alpha_{2i,j}$ and
$\alpha_{2i+1,j}$, for $0 \leq j \leq k-2$.
Next, add $(k-1)^2$ isolated vertices, $r_{i,j}$, $0 \leq i,j \leq k-2$, and
join $r_{i,j}$ to $\alpha_{h,t}$ if and
only if $\alpha_{h,t}$ is the $(j,h)$-entry
of the square $L_i$.
The construction continues by adding edges between each pair of
vertices $r_{i,2j}$ and $r_{i,2j+1}$,
resulting in $(k,5)$-graphs of order $2k^2 - 3k + 1$.
Finally, the construction is completed by removing all of the
vertices $r_{0,j}$ and adding edges between $\alpha_{4h,t}$ and
$\alpha_{4h+3,t}$, and between $\alpha_{4h+1,t}$ and $\alpha_{4h+2,t}$.

The resulting $(k,5)$-graph has order $2k^2 - 4k + 2$.

\Constr{amtar}{Araujo-Pardo and Montellano-Ballesteros}

The authors used finite projective and affine planes
to construct an infinite family 
of regular graphs of girth five
and degree $k$ \cite{araujoieee}.
Their construction gives the strongest results
when the degree $k=p+2$, for a prime $p$,
which matches the previous result
of O'Keefe and Wong of order $2k^2 - 8k + 8$. 

In the general case, where $k-2$ is not a prime,
their bound is
\[
n(k,5) \leq  \left\{ 
\begin{array}{ll}
 4(k-2)^2, & \mbox{ when } 7 \leq k \leq 3276, \\
 2(k-2)(k-1)(1+\frac{1}{2\ln^2(k-1)}), & \mbox{ when } 3276 < k. \\
\end{array}
\right.
\]

We present their general construction, an explicit
presentation of the
original \hyperlink{brotar}{construction of Brown}.
Consider the case where
the degree $k$ is less than the next prime $p$, and
let $A_p$ be the affine plane of order $p$.
Define a smaller incidence structure $A_{k,p}$ as follows.
The points of $A_{k,p}$ are the points of the affine
plane whose first coordinates are less than $k-2$.
The lines of $A_{k,p}$ are those whose slopes
are less than $k-2$.  The incidence graph of this
structure has order $2kp$, degree $k-2$ and girth $6$.
Now add edges joining pairs of points
whose first coordinates are equal
and  whose second
coordinates differ by $1$.
Similarly join pairs of lines whose slopes
are equal and whose $y$-intercepts
differ by $2$.

The resulting graph has girth $5$.
The precise form of their bound follows by using
a new result on
the distribution of primes
\cite{dusart}.

\Constr{jortar}{J{\o}rgensen}

J{\o}rgensen \cite{jorgensen} used relative difference sets
to construct several infinite families 
of regular graphs of girth five.
The best of these have degree $k=q+3$ (for prime power $q$)
and order $2k^2 - 12k + 16$.

His two general theorems can be summarized as follows.

\begin{theorem}[\cite{jorgensen}] \label{jorgthm}
Let $q$ be a prime power.  Then
\[
n(k,5) \leq  \left\{ 
\begin{array}{ll}
 2(k-1)(q-1), & \mbox{for }  7 \leq q, \;\; k \leq q + 2, \\
 2(k-2)(q-1), & \mbox{for } 13 \leq q, \;\; k \leq q + 3, \mbox{ and }q\mbox{ odd}. \\
\end{array}
\right.
\]
\end{theorem}

J{\o}rgensen's constructions are based on the
concept of a relative difference set.
Let $G$ be a finite group with a normal subgroup $H \triangleleft G$.
A subset $D \subset G$ is called
a {\em relative difference set} if
any element $ g \in G - H $ can be expressed uniquely
as a difference using elements from $D$, $g = x - y$, $x,y \in D$,
but no element of $H$ can be expressed in this manner.

J{\o}rgensen's construction starts with a finite
group $G$, a normal subgroup $H \triangleleft G$,
a set of coset representatives $T = \{a_1 , \dots , a_k\}$
for $H$ in $G$, and
a relative difference set $D$ for $H$ in $G$.
In addition, it also requires
two \hyperlink{cayref}{Cayley graphs}
on $H$ of girth $5$,
$C(H,S_1)$ and $C(H,S_2)$, such that
$S_1 \cap S_2 = \emptyset$.

Once one has all these ingredients,
a graph on the vertex set $G \times \{1,2\}$
can be constructed by introducing edges of
three types.

{\em
\begin{description}
\item{Type I.1:} $(ha_i,1)$ is adjacent to $(hxa_i,1)$ for all $h \in H$, $x \in S_1$, $a_i \in T$,
\item{Type I.2:} $(ha_i,2)$ is adjacent to $(hxa_i,2)$ for all $h \in H$, $x \in S_2$, $a_i \in T$,
\item{Type II:} $(g,1)$ is adjacent to $(gy,2)$ for all $g \in G$ and $y \in D$.
\end{description}
}

Note that the first two types create multiple copies of the
original Cayley graphs on the cosets of $H$ in $G$.

To obtain the bounds in Theorem~\ref{jorgthm}, one
needs to make specific choices for $G$, $H$, $T$, $S_1$ and
$S_2$.
For the first of the inequalities, J{\o}rgensen took
$G$ to be the cyclic group of order
$(q+1)(q-1)$, $H$ to be the cyclic subgroup of order $(q-1)$,
$T$ to be any complete set of coset representatives for
$H$ in $G$, and $D$ to be a relative difference set of 
size $q-1$ whose existence is guaranteed by the results
of Bose \cite{bose} and Elliot and Butson \cite{ellbut}.
The two Cayley graphs in this case are edge disjoint cycles
on the vertices of $H$.

For example, using this method with the choices 
$G = {\Bbb Z}_5 \times {\Bbb Z}_5$,
$H = {\Bbb Z}_5 \times \{0\}$, $S_1 = \{(1,0),(4,0)\}$, $S_2 = \{(2,0),(3,0)\}$,
$T = \{(0,0),(0,1),(0,2),(0,3),(0,4)\}$, and $D = \{(0,0),(1,1),(4,2),(4,3),(1,4)\}$,
results in yet another construction for the Hoffman-Singleton Graph.

For the second inequality in Theorem~\ref{jorgthm}, one proceeds
along similar lines using dihedral groups.

\subsubsection{Constructions for Girth 6, 8, and 12}
\label{con6812}

When $k-1$ is a prime power and $g=6,8$, or $12$, the $(k,g)$-cage
is known, and is the incidence graph of the generalized
$n$-gon, for $n=3,4$, or $6$, respectively (see \ref{geomref}).
In this section, we discuss constructions for
degrees $k$ where no generalized $n$-gon is known.
A number of different constructions for these values are
obtained by removing particular sets of vertices from
the incidence graphs of the generalized $n$-gons.
This might be compared to the situation for girth $5$ where
the cages $(3,5)$, $(5,5)$ and $(6,5)$ can be constructed
by removing vertices from the Hoffman-Singleton graph (see \ref{hoffsing2}),
which is the $(7,5)$-cage \cite{wongsurvey}.

In \cite{gacs},
G\' acs and H\' eger present a unified view of these constructions
using the concept of a $t$-{\em good structure}.
A $t$-good structure in a generalized  $n$-gon is a pair
$(P,L)$ consisting of a set of points $P$, and a set of
lines $L$, subject to the condition that there are $t$ lines
in $L$ through any point not in $P$, and $t$ points in $P$
on any line not in $L$.
Removing the points and lines of a $t$-good structure
from the incidence graph of a generalized $n$-gon
results in a $(q+1-t)$-regular graph of girth at least $2n$.

\Constr{bro2tar}{Brown}

Brown \cite{brownham} was the first who explicitly considered the 
case of girth $6$, and most subsequent constructions are directly or
indirectly derived from his. His construction can be stated in the
language of $t$-good structures as follows.

He begins with a
$1$-good structure consisting of a set of points
$P = \{ p_0 , \dots , p_q \}$ and
a set of lines $L = \{ \ell_0 , \dots , \ell_q \}$,
such that $p_0$ is incident with all the lines in $L$ and
$\ell_0$ is incident with all the points in $P$, and removes
it from $PG(2,q)$.
The incidence graph of the resulting geometry is
a $q$-regular graph of girth $6$ and order $2q^2$.

For $t>1$, he also removes all the neighbors of $p_1, \ldots, p_{t-1}$
and $\ell_1, \ldots, \ell_{t-1}$
to obtain a geometry whose incidence graph has girth (at least) $6$,
whose degree is $q-t+1$, and whose order is $2q(q-t+1)$.
He then uses Bertrand's postulate that asserts for every $k>2$ the existence 
of a prime $p$ such that $k < p < 2k$ \cite{harwri} to show that $n(k,6) <
4k^2 $, for all $k$, and other number theoretic results to show that for any
$\epsilon > 0 $ there exists and integer $N$ such that for all $k>N$, 
$n(k,6) < 2(1+\epsilon)k^2$. Note that $M(k,6)=2k^2-2k+2$.

\Constr{agmstar}{Araujo, Gonz\'{a}lez, Montellano-Ballesteros, Serra}

In \cite{araujoetal},
Araujo, Gonz\'{a}lez, Montellano-Ballesteros, and Serra
apply Brown's construction to generalized quadrangles
and hexagons, and obtain the following bounds which are
valid for $g = 6, 8,$ or $12$.

\[
n(k,g) \leq 2kq^{\frac{g-4}{2}}
\]

By using recent results on the distribution of primes they
obtain:

\[
n(k,g) \leq  \left\{ 
\begin{array}{ll}
 2k(k-1)^{\frac{g-4}{2}}(\frac{7}{6})^{\frac{g-4}{2}}, & 7 \leq k \leq 3275 \\
 2k(k-1)^{\frac{g-4}{2}}(1 + \frac{1}{2\ln^2(k)})^{\frac{g-4}{2}}, & 3276 \leq k. \\
\end{array}
\right.
\]

\Constr{aflntar}{Abreu, Funk, Labbate, Napolitano}

In \cite{abreu}, Abreu, Funk, Labbate, and Napolitano construct
several families of regular graphs of girth $6$.  Their constructions
make use of the addition and multiplication tables of ${\Bbb F}_q$.
We describe two of them using the language of G\' acs and H\' eger
\cite{gacs}.

In the first construction, let $(p_1,\ell_1)$ be a
non-incident point-line pair.  Choose $t-1$ points on
$\ell_1$: $p_2, \dots , p_t$; and choose $t-1$ lines through
$p_1$: $\ell_2 , \dots , \ell_t$.  The pair $(P,L)$, where 
$P$ is the set of all points on any of the lines $\ell_i$, and
$Q$ is the set of all lines through any of the points $p_i$,
is a $t$-good set.  Removing $(P,L)$ from $PG(2,q)$ leaves a
geometry whose incidence graph is $q-t+1$-regular, has
girth at least $6$, and order $2(q^2 + (1-t)q + (t-2))$.

The second construction requires the concept of a
{\em Baer subplane} $({\cal P}',{\cal L}')$ of a projective
plane $({\cal P},{\cal L})$, which is a subplane satisfying the
property that any point $p \not \in {\cal P}'$ is incident
with exactly one line in ${\cal L}$, and any line $ \ell \not \in
{\cal L}' $ is incident with exactly one point in ${\cal P}'$.
Baer subplanes of $PG(2,q)$ exist whenever $q$ is a square.
In fact, 
it is known that such planes
can be partitioned into $q - \sqrt{q} + 1$ disjoint
Baer subplanes \cite{hirsch}.
Note that a Baer subplane is a $1$-good structure.
To obtain a $t$-good structure,
$1 \leq t \leq q - \sqrt{q} + 1$,
use $t$ disjoint Baer subplanes.
The resulting graph is $q - t + 1$-regular, has
girth at least $6$, and order $2(q^2 + (1-t)q - t\sqrt{q} + (1-t))$.

\Constr{bgtar}{Bretto, Gillibert}  

A construction for $(k,6)$ and $(k,8)$-graphs was given by
Bretto and Gillibert \cite{french}.
They construct graphs $\Phi(G,S,m)$, with $G$ a
finite group, $S$ a non-empty subset of $G$, and
$m$ a positive integer.
Each $s \in S$ defines a partition
$G = \cup_{x \in T_s} \left<s\right>x$,
where $T_s$ is a complete set of right coset representatives
of $\left<s\right>$, the subgroup generated by $s$.

The vertices of $\Phi(G,S,m)$ are the cosets $\left<s\right>x$ of the
subgroups $\left<s\right>$ generated by elements of $S$.
Two such cosets are adjacent if the cardinality of their
intersection is $m$.

For example, they choose $G$ to be the Klein group, ${\Bbb Z}_2 \times {\Bbb Z}_2$.
The elements of $G$ are $\{1, a, b, ab\}$.
Take $S = \{a, b, ab\}$.  Then the cosets of
$a$ are $\{1,a\}$ and $\{b,ab\}$;
the cosets of $b$ are $\{1,b\}$ and $\{a,ab\}$; and the
cosets of $ab$ are $\{1,ab\}$ and $\{a,b\}$.  Taking
$m = 1$, we obtain the octahedral graph.

Using the nonabelian groups of order $p^3$ in which every
nonidentity element has order $p$, one can construct
$(p,6)$-graphs of order $2p^2$.
Note that this order is the same as the order obtained by
Brown \cite{brownham}.

Similarly, they employed a semidirect product
of $Z_p^3$ by $Z_p$ to
construct $p$-regular graphs of
girth $8$ and order $2p^3$ in the
cases where $k$ is a prime.

\Constr{ghtar}{G\' acs, H\' eger}

Applying their concept of a $t$-good structure to
generalized $4$-gons and $6$-gons, G\' acs and H\' eger
constructed graphs which
establish the following two bounds for prime powers $q$.

\begin{equation}\label{gacshegerthm}
\begin{array}{lcll}
n(q,8) & \leq & 2(q^3 - 2q), & q \mbox{ odd } \\
n(q,8) & \leq & 2(q^3 - 3q -2), & q \mbox{ even } \\
n(q,12) & \leq & 2(q^5 - q^3) &
\end{array}
\end{equation}

\Constr{balbuena8}{Balbuena}
 
This construction
is based on Latin squares and
covers a case for girth $8$ not
included in the above upper bound of
G\' acs and H\' eger.
She proves that for
degree $k \leq q$, and $q$ a prime power
$n(k,8) \leq 2q(qk-1)$ \cite{balbuena8}.

\hypertarget{exooexcision}{}
\subsubsection{Excision}
\label{excision}
Several of the above constructions are obtained
by removing vertices and incident edges from known
small $(k,g)$-graphs.

More precisely, let $G$ be a $(k,g)$-graph and let
$H$ be a subgraph of $G$ with degree set $\{1,k\}$.
Removing the vertices of $H$
whose degrees (in $H$) are $k$, together with
their adjacent edges,
leaves a subgraph of
$G$ containing vertices of degree $k-1$.
In the case $k=3$, one can suppress the resulting
vertices of degree $2$.
For larger values of $k$,
the final step involves pairing the degree $k-1$ vertices and
joining them with edges.
The goal is to find subgraphs $H$ whose removal leaves a graph whose
girth is {\em at least} $g-1$.
This process is an example of a class of constructions
usually referred to as {\em excision}.

The pioneering use of this kind of excision
was the construction of the $(3,11)$-cage, due to
Balaban \cite{balaban}, wherein he removed a
small subtree from the $(3,12)$-cage.

\hypertarget{araujo}{}
Araujo-Pardo \cite{araujo} applied a type of excision
to incidence graphs of generalized
polygons to obtain graphs whose girth is one less than
that of the original incidence graph.
In particular, the examples constructed in her paper give
$rec(5,11) = 2688$, $rec(9,7) = 1152$, and $rec(9,11) = 74752$.

\hypertarget{abtar}{}
Another Araujo-Pardo and Balbuena
girth $6$ excision construction \cite{arabal2}
applies to any
degree $k$.  Let $q$ be the smallest prime
power greater than $k$, then the authors show
$n(k,6) \leq 2(qk - 2)$.

Similarly, Araujo-Pardo, Balbuena and H\'{e}ger
apply Brown's excision method to
girth $6$, $8$, and  $12$ \cite{arabalheg}.
For girth $12$, and $q$ a prime power larger than $3$,
they obtain a result for degree $k \leq q$.

\begin{equation}\label{arabalthm}
\begin{array}{lcl}
n(k,12) \leq 2kq^2(q^2 - 1)
\end{array}
\end{equation}

The $rec(3,21)$, $rec(3,23)$, and $rec(3,25)$-graphs
were also obtained using excision \cite{exooweb},
as were the $rec(3,29)$-graph \cite{girthlift} and
the $rec(3,31)$-graph \cite{brayetal}.

\subsection{Individual Constructions} \label{indcon}

\subsubsection{Individual Constructions for Degree 3}
The orders of the trivalent cages of girth 13 and up are all unsettled.
The following table shows the current state of knowledge of degree up to $32$.
Note that for the sake of completeness we have also included the known cages 
for girths $5$ through $12$.
In cases where the lower and upper bounds were established
independently, the authors responsible for the lower bounds
are listed first, and separated by a semi-colon from the
authors responsible for the upper bound.

\hypertarget{trivalenttable}{}
\begin{center}
\begin{tabular}{|r|r|r|r|l|} \hline
Girth &  Lower & Upper & \# of & Due to  \\ 
$g$   & Bound  & Bound & Cages & \\
\hline \hline
 5 & 10 &  \hyperlink{cage35tar}{10} & 1 & Petersen \\ 
 6 & 14 &  \hyperlink{cage36tar}{14} & 1 & Heawood \\ 
 7 & 24 &  \hyperlink{cage37tar}{24} & 1 & McGee \\ 
 8 & 30 &  \hyperlink{cage38tar}{30} & 1 & Tutte \\ 
 9 & 58 &  \hyperlink{cage39tar}{58} & 18 & Brinkmann-McKay-Saager  \\ 
10 & 70 &  \hyperlink{cage310tar}{70} & 3 & O'Keefe-Wong  \\ 
11 & 112 &  \hyperlink{cage311tar}{112} & 1 & McKay-Myrvold; Balaban  \\ 
12 & 126 &  \hyperlink{cage312tar}{126} & 1 & Benson \\ 
13 & 202 & \hyperlink{rec313}{272} &   & McKay-Myrvold; Hoare  \\ 
14 & 258 & \hyperlink{rec314}{384} &   & McKay; Exoo  \\ 
15 & 384 & \hyperlink{rec315}{620} &   & Biggs  \\ 
16 & 512 & \hyperlink{rec316}{960} &    & Exoo  \\ 
17 & 768 & \hyperlink{rec317}{2176} &    & Exoo  \\ 
18 & 1024 & \hyperlink{rec318}{2560} &   & Exoo  \\ 
19 & 1536 & \hyperlink{rec319}{4324} &   & Hoare, H(47)  \\ 
20 & 2048 & \hyperlink{rec320}{5376} &   & Exoo  \\ 
21 & 3072 & \hyperlink{rec321}{16028} &   & Exoo  \\ 
22 & 4096 & \hyperlink{rec322}{16206} &   & Biggs-Hoare, S(73)  \\ 
23 & 6144 & \hyperlink{rec323}{49326} &   & Exoo \\ 
24 & 8192 & \hyperlink{rec324}{49608} &   & Bray-Parker-Rowley  \\ 
25 & 12288 & \hyperlink{rec325}{108906} &   & Exoo \\ 
26 & 16384 & \hyperlink{rec326}{109200} &   & Bray-Parker-Rowley  \\ 
27 & 24576 & \hyperlink{rec327}{285852} &   & Bray-Parker-Rowley  \\ 
28 & 32768 & \hyperlink{rec328}{415104} &   & Bray-Parker-Rowley  \\ 
29 & 49152 & \hyperlink{rec329}{1141484} &   & Exoo-Jajcay \\ 
30 & 65536 & \hyperlink{rec330}{1143408} &   & Exoo-Jajcay \\ 
31 & 98304 & \hyperlink{rec331}{3649794} &   & Bray-Parker-Rowley  \\ 
32 & 131072 & \hyperlink{rec332}{3650304} &   & Bray-Parker-Rowley  \\ \hline \hline 
\end{tabular}
\end{center}

\begin{center}
\vspace{3 mm}
\noindent
{\bf Table 3. } Bounds for trivalent cages.
\end{center}

\bigskip
Next, we briefly describe the graphs from the above table that are
not cages.

\Record{rec313}{3}{13}{272}

\noindent
The smallest known trivalent graph of girth $13$ has $272$ vertices and
is a Cayley graph (see \ref{cayref}) of the group of transformations
of the affine plane over ${\Bbb F}_{17}$.
Biggs reports \cite{biggsny} that the graph was discovered by Hoare.
Royle \cite{royle} has shown that a smaller
$(3,13)$-graph cannot be a Cayley graph.

\Record{rec314}{3}{14}{384}

\noindent
The smallest known trivalent graph of girth $14$ and order $384$
was constructed by Exoo \cite{exoo14}
It is a lift (see \ref{voltref}) of the multigraph shown in
\hyperlink{girth14fig}{Figure~\ref{girth14}}.

\hypertarget{girth14fig}{}
\begin{figure}[ht]
\centering
\includegraphics[width=6cm]{girth14.png}
\caption{Base graph for girth 14}\label{girth14fig}
\label{girth14}
\end{figure}

The voltage group used in the construction
is a semidirect product of the cyclic group
of order $3$ by the generalized quaternion group of order $16$,
and is SmallGroup(48,18) in the Small Group Library in
GAP \cite{gap}.
The automorphism group of this graph has order $96$.

\Record{rec315}{3}{15}{620}

\noindent
The smallest known trivalent graph of girth $15$ has $620$ vertices and
is the sextet graph (see \ref{sextetref}), S(31),
discovered by Biggs and Hoare \cite{sextet}.
The automorphism group of this graph has order $14880$.

\Record{rec316}{3}{16}{960}

\noindent
The smallest known trivalent graph of girth $16$ has $960$ vertices
and was discovered by Exoo \cite{exoo16}.
The graph is a lift (see \ref{voltref}) of the Petersen graph with voltage
assignments in ${\Bbb Z}_2 \times {\Bbb Z}_{48}$. In
\hyperlink{girth16fig}{Figure~\ref{girth16}} the
voltages assigned to each edge are given.
Unlabeled edges are assigned the group identity $(0,0)$.
The automorphism group of this graph has order $96$.

\hypertarget{girth16fig}{}
\begin{figure}[ht]
\centering
\includegraphics[width=6cm]{girth16.png}
\caption{Base graph for girth 16}\label{girth16fig}
\label{girth16}
\end{figure}

\Record{rec317}{3}{17}{2176}

\noindent
The smallest known trivalent graph of girth $17$ has order $2176$
and was discovered by Exoo \cite{exoo18}.
It is a lift (see \ref{voltref}) of the multigraph shown in
\hyperlink{girth17fig}{Figure~\ref{girth17}}.
The voltage group is a group of order $272$ 
and is SmallGroup(272,28) in the
GAP Small Group Library \cite{gap}.
Note that the group is not the affine group of the same order
that was used by Biggs and Hoare in the construction of the
$(3,13)$-graph discussed above.
The automorphism group of this graph has order $544$.

\hypertarget{girth17fig}{}
\begin{figure}[ht]
\centering
\includegraphics[width=5cm]{girth17.png}
\caption{Base graph for girth 17}\label{girth17fig}
\label{girth17}
\end{figure}

\Record{rec318}{3}{18}{2560}

\noindent
The smallest known trivalent graph of girth $18$
has $2560$ vertices and was discovered by Exoo \cite{exoo18}.
It is a lift (see \ref{voltref}) of the multigraph in
\hyperlink{girth18fig}{Figure~\ref{girth18}}.
The voltage group has order $320$,
and is SmallGroup(320,696) in the
GAP Small Group Library \cite{gap}.
The maximum order among group elements is $20$.
The Sylow $2$-subgroups are nonabelian with exponent $8$.
The Sylow $5$-subgroup is normal, and so the full group
is a semi-direct product. 
The automorphism group of the graph has order $640$.

\hypertarget{girth18fig}{}
\begin{figure}[ht]
\centering
\includegraphics[width=6cm]{girth18.png}
\caption{Base graph for girth 18}\label{girth18fig}
\label{girth18}
\end{figure}

\Record{rec319}{3}{19}{4324}

\noindent
The smallest known trivalent graph of girth $19$
has order $4324$.
It is the Hexagon graph (see \ref{hexgraphref}), H(47),
discovered by Hoare \cite{hexagon}.
The automorphism group of the graph has order $51888$.

\Record{rec320}{3}{20}{5376}

\noindent
The smallest known trivalent graph of girth $20$ has
order $5376$ and was discovered by Exoo \cite{exoo18}.
It is a lift (see \ref{voltref}) over the multigraph
of order two and size three, with the three edges joining
the two vertices.  The voltage group is a group
of order $2688$.  The automorphism group of the graph
has order $5376$ and is transitive on the vertices.
The graph turns out to be a Cayley graph,
and hence, a graphical regular representation \cite{handbook}.

\Record{rec321}{3}{21}{16028}

\noindent
The smallest known trivalent graph of girth $21$ has
order $16028$ and was obtained by Exoo \cite{exooweb}
using \hyperlink{exooexcision}{excision} on S(73) \cite{sextet}.

\Record{rec322}{3}{22}{16206}

\noindent
The smallest known trivalent graph of girth $22$ has
order $16206$ and is the
sextet graph (see \ref{sextetref}), S(73),
discovered by Biggs and Hoare \cite{sextet}.

\Record{rec323}{3}{23}{49326}

\noindent
The smallest known trivalent graph of girth $23$
was discovered by Exoo \cite{exooweb} and
was obtained
by \hyperlink{exooexcision}{excision} from
the graph 
\hyperlink{bprtar}{$B(PSL(2,53) \times {\Bbb Z}_2, \{ \alpha, \delta, \delta^{-1} \}) $}
defined next.
It is of order $49326$.

\Record{rec324}{3}{24}{49608}

\noindent
The smallest known trivalent graph of girth $24$
was discovered by Bray, Parker and Rowley \cite{brayetal}.
It is the graph
\hyperlink{bprtar}{$B(PSL(2,53) \times {\Bbb Z}_2, \{ \alpha, \delta, \delta^{-1} \}) $}
of order $49608$.
The generating permutations $\alpha$ and $\delta$
are as follows.

\noindent
$\alpha:$
\begin{verbatim}
  ( 1, 4)( 2, 5)( 3, 6)( 7,23)( 8,16)( 9,14)(10,24)(11,46)
  (12,21)(15,32)(17,47)(18,41)(19,49)(20,55)(22,29)(25,48)
  (26,36)(27,38)(28,39)(30,40)(31,35)(33,60)(34,51)(37,44)
  (42,56)(43,59)(45,54)(50,58)(52,57)
\end{verbatim}

\noindent
$\delta:$
\begin{verbatim}
  ( 7,49,12)( 8,52,57)( 9,35,44)(10,34,18)(11,53,48)(13,56,55)
  (14,17,21)(15,31,38)(16,25,51)(19,60,40)(20,54,41)(22,29,45)
  (23,24,32)(26,50,42)(27,33,30)(28,36,37)(39,43,46)(47,59,58)
\end{verbatim}

\Record{rec325}{3}{25}{108906}

\noindent
The smallest known trivalent graph of girth $25$ 
is of order $108906$ and
was obtained by Exoo \cite{exooweb}
using
\hyperlink{exooexcision}{excision} from
\hyperlink{bprtar}{
$ B((PSL(2,25) \times 7:3 ): 2, \{ \alpha, \delta, \delta^{-1} \}) $}
defined next.

\Record{rec326}{3}{26}{109200}

\noindent
The smallest known trivalent graph of girth $26$
is of order $109200$.
It is the graph 
\hyperlink{bprtar}{$B((PSL(2,25) \times 7:3 ): 2, \{ \alpha, \delta, \delta^{-1} \}) $}
discovered by Bray, Parker and Rowley \cite{brayetal}.
The generating permutations $\alpha$ and $\delta$
are as follows.

\noindent
$\alpha:$
\begin{verbatim}
  ( 2, 7)( 3, 6)( 4, 5)( 8,18)( 9,20)(10,17)(11,12)(13,32)
  (14,29)(15,31)(16,25)(19,21)(22,26)(23,27)(24,33)(28,30)
\end{verbatim}

\noindent
$\delta:$
\begin{verbatim}
  ( 1, 7, 5)( 3, 4, 6)( 8,15,30)( 9,32,11)(10,27,22)(13,24,26)
  (14,21,25)(16,29,31)(18,23,20)(19,33,28)
\end{verbatim}

\Record{rec327}{3}{27}{285852}

\noindent
The smallest known trivalent graph of girth $27$
is of order $285852$.
It is the graph
\hyperlink{bprtar}{$B(PSL(2,83) \times {\Bbb Z}_3, \{ \alpha, \delta, \delta^{-1} \}) $}
discovered by Bray, Parker and Rowley \cite{brayetal}.
The generating permutations $\alpha$ and $\delta$
are as follows.

\noindent
$\alpha:$
\begin{verbatim}
  ( 7,14)( 8,73)( 9,24)(10,89)(11,23)(12,60)(13,87)(15,76)
  (16,68)(17,25)(18,40)(19,64)(20,26)(21,43)(22,31)(27,67)
  (28,74)(29,79)(30,39)(32,66)(33,71)(34,78)(35,41)(36,44)
  (37,52)(38,50)(42,81)(45,77)(46,69)(47,54)(48,58)(49,85)
  (51,56)(53,72)(55,80)(57,70)(59,62)(61,63)(65,90)(75,88)
  (82,84)(83,86)
\end{verbatim}

\noindent
$\delta:$
\begin{verbatim}
  ( 1, 3, 5)( 2, 4, 6)( 7,38,65)( 8,30,43)( 9,64,18)(10,27,37)
  (11,31,72)(12,32,55)(13,35,84)(14,75,68)(15,51,57)(16,33,90)
  (17,49,19)(20,80,42)(21,66,40)(22,87,61)(23,85,47)(24,78,26)
  (25,63,34)(28,70,76)(29,59,52)(36,62,89)(39,79,86)(41,48,88)
  (44,58,77)(45,73,81)(46,54,82)(50,69,83)(53,56,67)(60,71,74)
\end{verbatim}

\Record{rec328}{3}{28}{415104}

\noindent
The smallest known trivalent graph of girth $28$
is of order $415104$.
It is the graph \hyperlink{bprtar}{$B(PGL(2,47) \times Alt(4),
\{ \alpha, \delta, \delta^{-1} \}) $}
discovered by Bray, Parker and Rowley \cite{brayetal}.
The generating permutations $\alpha$ and $\delta$
are as follows.

\noindent
$\alpha:$
\begin{verbatim}
  ( 1, 4)( 2, 3)( 5,20)( 6,52)( 7,45)( 8,12)( 9,28)(10,32)
  (11,33)(13,47)(14,42)(15,34)(16,22)(17,24)(18,41)(19,26)
  (21,27)(23,38)(25,50)(29,49)(30,44)(31,35)(36,46)(37,39)
  (43,48)
\end{verbatim}

\noindent
$\delta:$
\begin{verbatim}
  ( 1, 4, 2)( 5,33,11)( 6,30,17)( 7,19,21)( 8,38,45)( 9,34,39)
  (10,37,20)(12,14,26)(13,44,23)(15,35,31)(16,51,27)(18,50,46)
  (22,48,28)(24,42,47)(25,36,43)(29,32,41)(40,49,52)
\end{verbatim}

\Record{rec329}{3}{29}{1141484}

\noindent
The smallest known trivalent graph of girth $29$
is of order $1141484$ and was
constructed by Exoo and Jajcay \cite{girthlift}.
It was obtained by
\hyperlink{exooexcision}{excision}
from the girth $30$ graph described
in the \hyperlink{girth30}{next section}.
This improves the bound of
$1143408$
%% \hyperlink{bprtar}{
%% $ B(PGL(2,83) \times Alt(4), \{ \alpha, \delta, \delta^{-1} \}) $}
due to Bray, Parker and Rowley \cite{brayetal}.
%% The generating permutations $\alpha$ and $\delta$
%% are as follows.

%% \noindent
%% $\alpha:$
%% \begin{verbatim}
%%   ( 1, 3)( 2, 4)( 5, 6)( 7,42)( 8,73)( 9,69)(10,62)(11,43)
%%   (12,36)(13,32)(14,63)(15,16)(17,34)(18,86)(19,87)(20,27)
%%   (21,77)(22,33)(23,44)(24,79)(25,66)(26,81)(28,84)(29,41)
%%   (30,67)(31,65)(35,53)(37,46)(38,75)(39,80)(40,74)(45,48)
%%   (47,55)(49,51)(50,58)(52,70)(54,56)(57,60)(59,68)(61,82)
%%   (64,76)(71,88)(72,83)(78,85)
%% \end{verbatim}
%% 
%% \noindent
%% $\delta:$
%% \begin{verbatim}
%%   ( 2, 4, 3)( 5,10,49)( 6,26,77)( 7,41,24)( 8,53,50)( 9,85,75)
%%   (11,44,45)(12,78,80)(13,28,60)(14,23,81)(15,71,69)(16,19,62)
%%   (17,31,66)(18,46,56)(20,35,72)(21,68,74)(22,42,55)(25,34,51)
%%   (27,58,64)(29,32,70)(30,76,86)(33,63,61)(36,52,54)(37,87,88)
%%   (38,43,83)(39,57,47)(40,82,79)(48,59,67)(65,73,84)
%% \end{verbatim}

\hypertarget{girth30}{}
\Record{rec330}{3}{30}{1143408}

\noindent
The smallest known trivalent graph of girth $30$ and
order $83^3 - 83 = 1143408$
was constructed by Exoo and Jajcay \cite{girthlift}.
It is a voltage graph lift of
the \hyperlink{theta}{$\theta$-graph} of order $2$ using the group $SL(2,83)$
and the voltages $1$, $a$, and $b$, where:
\[  a = \left( \begin{array}{rr} 0 & 1 \\ -1 & 6 \end{array} \right) , \;\;
b = \left( \begin{array}{cc} 1 & 11 \\ 23 & 5 \end{array} \right). \]
The elements $a$ and $b$ are conjugates of order $84$.
The graph is vertex-transitive and the size of its
automorphism group is twice the size of the graph.
The previous record holder was
the sextet graph of Biggs and Hoare \cite{sextet}, S(313), of
order $1227666$ (see \ref{sextetref}).

\Record{rec331}{3}{31}{3649794}

\noindent
The smallest known trivalent graph of girth $31$ 
is of order $3649794$ and
was obtained by Bray, Parker and Rowley \cite{brayetal},
using excision, from
the graph
\hyperlink{bprtar}{
$B(PGL(2,97) \times Alt(4), \{ \alpha, \delta, \delta^{-1} \}) $}
defined next.

\noindent

\Record{rec332}{3}{32}{3650304}

\noindent
The smallest known trivalent graph of girth $32$
is of order $3650304$.
It is the graph 
\hyperlink{bprtar}{$B(PGL(2,97) \times Alt(4), \{ \alpha, \delta, \delta^{-1} \}) $}
discovered by Bray, Parker and Rowley \cite{brayetal}.
The generating permutations $\alpha$ and $\delta$
are as follows.

\noindent
$\alpha:$
\begin{verbatim}
  ( 1,  3)( 2,  4)( 5, 34)( 6, 91)( 7, 22)( 8, 45)( 9, 66)
  (10, 41)(11, 95)(12, 88)(13, 67)(14, 80)(15, 19)(16, 17)
  (18, 68)(20, 30)(21, 26)(23, 31)(24, 61)(25, 71)(27, 65)
  (28, 59)(29, 36)(32, 97)(33, 40)(35, 64)(37, 70)(38, 46)
  (39, 49)(42,102)(43, 48)(44, 96)(47, 62)(50, 54)(51, 99)
  (52, 53)(55, 87)(56,100)(57, 79)(58, 72)(60,101)(63, 76)
  (69, 86)(73, 92)(74, 83)(75, 94)(77, 89)(78, 90)(81, 98)
  (82, 85)(84, 93)
\end{verbatim}

\noindent
$\delta:$
\begin{verbatim}
  ( 2,  3,  4)( 5, 62, 69)( 6, 87, 20)( 7, 13, 49)( 8, 25, 79)
  ( 9, 56, 72)(10, 21, 33)(11, 19, 38)(12, 52, 44)(14, 39, 30)
  (15, 43, 81)(16, 97, 83)(17, 85, 29)(18, 86, 74)(22, 60, 88)
  (23, 28, 27)(24, 78, 95)(26, 67,100)(31, 47, 94)(32, 45, 42)
  (34, 41, 98)(35, 53, 46)(36, 77,101)(37,102, 55)(48, 99, 66)
  (50, 68, 57)(51, 91, 59)(54, 90, 96)(58, 71, 61)(64, 89, 73)
  (65, 84, 92)(70, 82, 93)(75, 80, 76)
\end{verbatim}

\hypertarget{missingmoore}{}
\subsubsection{Individual Constructions for Girth 5}
For graphs of degree $k$ and girth $5$, the Moore bound 
is $k^2 + 1$.  In this case there are Moore graphs for
degrees $3$, $7$, and perhaps $57$. The case $k=57$ is unresolved, and has 
received a lot of attention.
Aschbacher showed that there does not exist
a rank 3 permutation group with subdegree $57$.
This means that a Moore graph of degree $57$ is
not a rank 3 graph and is not distance
transitive.
In an unpublished work, G. Higman also
showed that such a graph is not
vertex-transitive \cite{cameron}.
Further restrictions on the automorphism group of
a potential Moore graph of degree $57$ were obtained
by Makhnev and Paduchikh \cite{makpad}, who showed
that if the automorphism group of such a graph
contains an involution, then the order of the
group must be relatively small.
Ma\v caj and \v Sir\' a\v n continued in this
direction and showed that the order of the automorphism group
of such a graph is at most $375$ \cite{macsir}.

The best currently known graphs of girth $5$ and degree up to $20$ are 
listed in the next table.

\begin{center} \label{girth5table}
\begin{tabular}{|r|r|r|l|l|} \hline
Degree &  Lower & Upper & Due to \\ 
$k$   & Bound  & Bound & \\
\hline \hline
3 & 10 & \hyperlink{cage35tar}{10} & Petersen \\ 
4 & 19 & \hyperlink{cage45tar}{19} & Robertson \\ 
5 & 30 & \hyperlink{cage55tar}{30} & Robertson-Wegner-Wong \\ 
6 & 40 & \hyperlink{cage65tar}{40} & Wong \\ 
7 & 50 & \hyperlink{cage75tar}{50} & Hoffman-Singleton \\ 
8 & 67 & \hyperlink{rec85}{80} & Royle \\ 
9 & 86 & \hyperlink{rec95}{96} & J{\o}rgensen \\ 
10 & 103 & \hyperlink{rec105}{124} & Exoo \\ 
11 & 124 & \hyperlink{rec115}{154} & Exoo \\ 
12 & 147 & \hyperlink{rec125}{203} & Exoo \\ 
13 & 174 & \hyperlink{rec135}{230} & Exoo \\ 
14 & 199 & \hyperlink{rec145}{288} & J{\o}rgensen \\ 
15 & 230 & \hyperlink{rec155}{312} & J{\o}rgensen \\ 
16 & 259 & \hyperlink{rec165}{336} & J{\o}rgensen \\ 
17 & 294 & \hyperlink{rec175}{448} & Schwenk \\ 
18 & 327 & \hyperlink{rec185}{480} & Schwenk \\ 
19 & 364 & \hyperlink{rec195}{512} & Schwenk \\ 
20 & 403 & \hyperlink{rec205}{576} & J{\o}rgensen \\ \hline
\end{tabular}
\end{center}

\begin{center}
\vspace{3 mm}
\noindent
{\bf Table 4. } Bounds for girth $5$ cages.
\end{center}

\bigskip
Next, we briefly describe the graphs from the above table that
are not cages.

\hypertarget{royletar}{}
\Record{rec85}{8}{5}{80}

\noindent
The smallest known $(8,5)$-graph
is of order $80$.
It was discovered by Royle \cite{royle},
and is a Cayley graph.
It can be constructed using either
SmallGroup(80,32) or SmallGroup(80,33)
in the GAP Small Group Library \cite{gap}.

\Record{rec95}{9}{5}{96}

\noindent
The smallest known $(9,5)$-graph, of
order $96$, was constructed by J{\o}rgensen \cite{jorgensen}
using a cyclic relative difference set.
The construction is from the first part of Theorem~\ref{jorgthm},
for the case $q=7$.
The group used is cyclic of order $48$, the subgroup
is cyclic of order $6$, and the relative difference set has size $6$.

\Record{rec105}{10}{5}{124}

\noindent
The smallest known $(10,5)$-graph has order $124$ and was
discovered by Exoo \cite{exooweb}.  It was found by a
computer search starting from a subgraph of the incidence graph of
a projective plane of order $11$.  The algorithm was
modeled after a method described by Abreu, Araujo-Pardo,
Balbuena and Labbate in \cite{aablgirth5}.

\Record{rec115}{11}{5}{154}

\noindent
The smallest known $(11,5)$-graph has order $154$ and was
discovered by Exoo \cite{exooweb}.

\Record{rec125}{12}{5}{203}

\noindent
The smallest known $(12,5)$-graph has order $203$ and was
discovered by Exoo \cite{exooweb}.
It is a Cayley graph of the semi-direct product
${\Bbb Z}_{29} \rtimes {\Bbb Z}_7$ (of order $203$),
whose full automorphism group is the same group again,
and hence, it is a graphical regular
representation \cite{handbook}.

\Record{rec135}{13}{5}{230}

\noindent
The smallest known $(13,5)$-graph has order $230$ and was
discovered by Exoo \cite{exooweb}.

\Record{rec145}{14}{5}{288}

\noindent
The smallest known $(14,5)$-graph, of
order $288$, was constructed by J{\o}rgensen \cite{jorgensen}
using a dihedral relative difference set.
The construction is from the second part of Theorem~\ref{jorgthm},
for the case $q=13$ and $k=14$.


\Record{rec155}{15}{5}{312}

\noindent
The smallest known $(15,5)$-graph, of
order $312$, was constructed by J{\o}rgensen \cite{jorgensen}
using a dihedral relative difference set.
The construction is from the second part of Theorem~\ref{jorgthm},
for the case $q=13$ and $k=15$.

\Record{rec165}{16}{5}{336}

\noindent
The smallest known $(16,5)$-graph, of
order $336$, was constructed by J{\o}rgensen \cite{jorgensen}
using a dihedral relative difference set.
The construction is from the second part of Theorem~\ref{jorgthm},
for the case $q=13$ and $k=16$.

\Record{rec175}{17}{5}{448}

\noindent
The smallest known $(17,5)$-graph has
order $448$, and was constructed by Schwenk \cite{schwenk}
from the \hyperlink{rec195}{$(19,5)$-graph} by
removing two copies of the M\" obius-Kantor graph
from each of the sets $P$ and $Q$.


\Record{rec185}{18}{5}{480}

\noindent
The smallest known $(18,5)$-graph has
order $480$, and was constructed by Schwenk \cite{schwenk}
from the \hyperlink{rec195}{$(19,5)$-graph} by
removing one copy of the M\" obius-Kantor graph
from each of the sets $P$ and $Q$.

\Record{rec195}{19}{5}{512}

\noindent
The smallest known $(19,5)$-graph has
order $512$, and was discovered by
Schwenk \cite{schwenk}.
The graph is constructed from two sets $P$ and $Q$ each
consisting of 16 copies, indexed by ${\Bbb F}_{16}$,
of the M\" obius-Kantor graph (see
\hyperlink{mobkantfig}{Figure~\ref{mobkantlab}}).
In addition, the vertices of each copy of the graph
are labeled by ${\Bbb F}_{16}$.
The remaining edges join vertices from copies in $P$ to
vertices from copies in $Q$ according to a rule based
on field operations in ${\Bbb F}_{16}$ analogous to
the rule used in Robertson's construction of the
Hoffmann-Singleton graph (see \ref{hoffsing2}).

\hypertarget{mobkantfig}{}
\begin{figure}[ht]
\centering
\includegraphics[width=5cm]{mobkant.png}
\caption{The M\" obius-Kantor graph}\label{mobkantfig}
\label{mobkantlab}
\end{figure}


\Record{rec205}{20}{5}{576}

\noindent
The smallest known $(20,5)$-graph, of
order $576$, was constructed by J{\o}rgensen \cite{jorgensen}
using a dihedral relative difference set.
The construction is from the second part of Theorem~\ref{jorgthm},
for the case $q=17$ and $k=20$.

\subsubsection{Individual Constructions for Girth 6}

When $k = q+1$, for a prime power $q$, the $(k,6)$-cage
is the incidence graph of a projective plane.
Outside these cases, there is only one case where
the order of the cage has been established, namely
$k = 7$ \cite{okwong6}.
The remaining cases listed in the following table
all come from infinite families discussed in
Section~\ref{con6812}.

\vspace{5mm}
\begin{center}
\begin{tabular}{|r|r|r|l|} \hline
   Degree &  Lower & Upper & Due to \\ 
    $k$   &  Bound & Bound & \\ \hline \hline
   3 & 14 & \hyperlink{projplane}{14} & Projective Plane \\ 
   4 & 26 & \hyperlink{projplane}{26} & Projective Plane \\ 
   5 & 42 & \hyperlink{projplane}{42} & Projective Plane \\ 
   6 & 62 & \hyperlink{projplane}{62} & Projective Plane \\ 
   7 & 90 & \hyperlink{cage76tar}{90} & O'Keefe-Wong \\ 
   8 & 114 & \hyperlink{projplane}{114} & Projective Plane \\ 
   9 & 146 & \hyperlink{projplane}{146} & Projective Plane \\ 
  10 & 182 & \hyperlink{projplane}{182} & Projective Plane \\ 
  11 & 224 & \hyperlink{wong11}{240} & Wong \\ 
  12 & 266 & \hyperlink{projplane}{266} & Projective Plane \\ 
  13 & 314 & \hyperlink{aflntar}{336} & Abreu-Funk-Labbate-Napolitano \\ 
  14 & 366 & \hyperlink{projplane}{366} & Projective Plane \\ 
  15 & 422 & \hyperlink{aflntar}{462} & Abreu-Funk-Labbate-Napolitano \\ 
  16 & 482 & \hyperlink{aflntar}{504} & Abreu-Funk-Labbate-Napolitano \\ 
  17 & 546 & \hyperlink{projplane}{546} & Projective Plane \\ 
  18 & 614 & \hyperlink{projplane}{614} & Projective Plane \\ 
  19 & 686 & \hyperlink{aflntar}{720} & Abreu-Funk-Labbate-Napolitano \\ 
  20 & 762 & \hyperlink{projplane}{762} & Projective Plane \\ \hline 
\end{tabular} 
\end{center}
\vspace{5mm}

\begin{center}
\vspace{3 mm}
\noindent
{\bf Table 5. } Bounds on cages of girth 6.
\end{center}

\subsubsection{Summary of Individual Constructions}

In the table below, we summarize the best known
upper bounds
for degrees up to $20$ and girths up to $16$.
Recall that entries for degree $3$ and girths greater than $16$
can be found in \hyperlink{trivalenttable}{Table 3}.

Most of the cases where there is an entry in the table that
does not appear in any of the previous tables
are for girths $8$ and $12$.
For these girth there is a cage known
whenever $k-1$ is a prime power.
All but two of the other entries for $8$ and $12$
come from G\' acs and H\' eger \cite{gacs}.
The entries, $(15,8)$ and $(15,12)$,
are due to Balbuena \cite{balbuena8} and
Araujo-Pardo, Balbuena and H\'{e}ger \cite{arabalheg}.
In addition,
the entries $(5,11)$, $(9,7)$ and $(9,11)$ are due to
Araujo-Pardo \cite{araujo}.
The four entries for girth $7$ consist of the two known
cages (degrees $3$ and $4$),
and two graphs constructed using excision
by McKay and Yuanshen \cite{mckpc}.
The remaining three entries, that have not appeared previously,
are for degree $4$ and girths $9$ and $10$, and for
degree $5$ and girth $10$ \cite{exooweb}.
\vskip 7mm

\hskip -14mm
\begin{tabular}{|c||r|r|r|r|r|r|r|r|r|r|r|r|r|} \hline \hline
$ k/g $ & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ \hline \hline
3 & \hyperlink{cage35tar}{10} & \hyperlink{cage36tar}{14} &
    \hyperlink{cage37tar}{24} & \hyperlink{cage38tar}{30} &
    \hyperlink{cage39tar}{58} & \hyperlink{cage310tar}{70} &
    \hyperlink{cage311tar}{112} & \hyperlink{cage312tar}{126} &
    \hyperlink{rec313}{272} & \hyperlink{rec314}{384} &
    \hyperlink{rec315}{620} & \hyperlink{rec316}{960} \\ 
4 & \hyperlink{cage45tar}{19} & \hyperlink{projplane}{26} &
    \hyperlink{cage47tar}{67} & \hyperlink{genquad}{80} &
    \hyperlink{exooweb}{275} & \hyperlink{exooweb}{384} &
         & \hyperlink{genhex}{728}  & & & & \\ 
5 & \hyperlink{cage55tar}{30} & \hyperlink{projplane}{42} &
    \hyperlink{mckpc}{152} & \hyperlink{genquad}{170} &
       & \hyperlink{exooweb}{1296}
       & \hyperlink{araujo}{2688}
       & \hyperlink{genhex}{2730}  & & & & \\ 
6 & \hyperlink{cage65tar}{40} & \hyperlink{projplane}{62} &
    \hyperlink{mckpc}{294} & \hyperlink{genquad}{312} &
       & &
       & \hyperlink{genhex}{7812}  & & & & \\ 
7 & \hyperlink{cage75tar}{50} & \hyperlink{cage76tar}{90} &
       & \hyperlink{exooweb}{672} &
       & &
       & \hyperlink{ghtar}{32928}  & & & & \\ 
8 & \hyperlink{rec85}{80} & \hyperlink{projplane}{114} &
       & \hyperlink{genquad}{800} &
       & &
       & \hyperlink{genhex}{39216}  & & & & \\ 
9 & \hyperlink{rec95}{96} & \hyperlink{projplane}{146}
       & \hyperlink{araujo}{1152}
       & \hyperlink{genquad}{1170} &
       &
       & \hyperlink{araujo}{74752}
       & \hyperlink{genhex}{74898}  & & & & \\ 
10 & \hyperlink{rec105}{124} & \hyperlink{projplane}{182} &
       & \hyperlink{genquad}{1640} &
       & &
       & \hyperlink{genhex}{132860}  & & & & \\ 
11 & \hyperlink{rec115}{154} & \hyperlink{wong11}{240} &
       & \hyperlink{ghtar}{2618} &
       & &
       & \hyperlink{ghtar}{319440}  & & & & \\ 
12 & \hyperlink{rec125}{203} & \hyperlink{projplane}{266} &
       & \hyperlink{genquad}{2928} &
       & &
       & \hyperlink{genhex}{354312}  & & & & \\ 
13 & \hyperlink{rec135}{230} & \hyperlink{aflntar}{336} &
       & \hyperlink{ghtar}{4342} &
       & &
       & \hyperlink{ghtar}{738192}  & & & & \\ 
14 & \hyperlink{rec145}{288} & \hyperlink{projplane}{366} &
       & \hyperlink{genquad}{4760} &
       & &
       & \hyperlink{genhex}{804468}  & & & & \\ 
15 & \hyperlink{rec155}{312} & \hyperlink{ghtar}{462} &
       & \hyperlink{balbuena8}{7648} &
       & &
       & \hyperlink{abtar}{1957376}  & & & & \\ 
16 & \hyperlink{rec165}{336} & \hyperlink{ghtar}{504} &
       & \hyperlink{ghtar}{8092} &
       & &
       & \hyperlink{ghtar}{2088960}  & & & & \\ 
17 & \hyperlink{rec175}{448} & \hyperlink{projplane}{546} &
       & \hyperlink{genquad}{8738} &
       & &
       & \hyperlink{genhex}{2236962}  & & & & \\ 
18 & \hyperlink{rec185}{480} & \hyperlink{projplane}{614} &
       & \hyperlink{genquad}{10440} &
       & &
       & \hyperlink{genhex}{3017196}  & & & & \\ 
19 & \hyperlink{rec195}{512} & \hyperlink{aflntar}{720} &
       & \hyperlink{ghtar}{13642} &
       & &
       & \hyperlink{ghtar}{4938480}  & & & & \\ 
20 & \hyperlink{rec205}{576} & \hyperlink{projplane}{762} &
       & \hyperlink{genquad}{14480} &
       & &
       & \hyperlink{genhex}{5227320}  & & & & \\ \hline 
\end{tabular}

\vspace{3 mm}
\begin{center}
\noindent
{\bf Table 6. } Summary of upper bounds for $n(k,g)$.
\end{center}

\section{Open Problems}
The central problem is that of determining
$n(k,g)$ and finding all the corresponding cages.
Since this is a very hard problem in general,
in what follows we list some subproblems on which progress
might be made.

Since upper bounds can be improved through graph constructions,
much more work has been done on the upper bounds for $n(k,g)$.
Our first problem calls for remedying this imbalance.

\begin{itemize}
\item[1.] {\em Improve the lower bounds on the order of cages in cases where a
Moore graph does not exist.}  Beside \cite{brown,kovacs,erosch},
very little progress has been made
on \hyperlink{lowerbounds}{lower bounds}.
\end{itemize}

Next, we address the relationship between the growth rate of
$n(k,g)$ and the Moore bound.
The following two problems are specific cases of this general
problem, one for fixed degree and one for fixed girth.

\begin{itemize}
\item[2.] {\em Find an infinite family of trivalent graphs \hyperlink{biggsfamily}{with large girth} $g$ and order
$2^{cg}$ for $c < \frac{3}{4}$.}
Note that in this case the Moore bound
is essentially $2^{\frac{1}{2}g}$, whereas the best known constructions
\cite{sextet,lubphisar,lazustwol2} are asymptotically of order $2^{\frac{3}{4}g}$.  
\item[3.] {\em Find infinite families of graphs of girth $10$, degree $k$, and 
with orders within a constant multiple of the Moore bound.}
For girths $5$, $6$, $8$, and $12$, such families are known.  Girth
$10$ appears to be the most approachable candidate for progress.
\end{itemize}

Progress on obtaining exact values for $n(k,g)$ for specific
values of $k$ and $g$ has been slow.
A few of these merit special mention.

\begin{itemize}
\item[4.] {\em Settle the existence question for the missing Moore graph,
which would be a $(57,5)$-cage of order $3250$.}  Such a graph cannot
be vertex-transitive and  \hyperlink{missingmoore}{its automorphism group}
can have order at most $375$.
\item[5.] {\em Improve the bounds on the value of $n(3,13)$, which have been
$202$ and $272$ for some time.}  Already in $1998$,
Biggs \cite{biggssurvey} stated that the
the failure to improve the upper bound of $272$ ``is becoming an embarassment".
\item[6.] {\em Determine the order of the $(8,5)$-cage.}  The $(k,5)$-cages, for
$k \leq 7$ have been known for over $30$ years. We currently know that
$ 66 \leq n(8,5) \leq \hyperlink{royletar}{80} $, where the upper bound is due to Royle \cite{royle}.
\end{itemize}

It has been frequently observed that it is much easier to construct
small regular graphs of even girth if one assumes in addition that the 
they are bipartite.
In fact, all known even girth cages and record holders are bipartite.
In Wong's $1982$ survey \cite{wongsurvey}, he asks if
every cage of even girth is bipartite.
A positive answer to this question was stated as a conjecture by Frank
Harary to the first author of this survey (when he was a graduate
student) in the $1970$'s.

\begin{itemize}
\item[7.] {\em Is every cage of even girth bipartite?}
\item[8.] {\em Find direct constructions for trivalent graphs of odd girth $g > 19$.}
Each of the entries in \hyperlink{tableone}{Table 1} for these girths was obtained
by excision from the bipartite record graph of even girth $g + 1$.
\end{itemize}

One can consider the cage problem in restricted contexts.
Of particular interest are the classes of Cayley
graphs and, more generally, of vertex-transitive graphs.
The vertex symmetry of these graphs makes the central
problem of finding cages more manageable, both for upper
and lower bounds.
For this reason, many of the current record
holders are highly symmetric.

\begin{itemize}
\item[9.] {\em Find the smallest vertex-transitive graphs of given degree $k$ and girth $g$.}
\end{itemize}

\appendix
\appendixpage

\section{Symmetric Graphs}
\label{symmref}
Many of the graphs discussed above exhibit a high level of symmetry.
All the known Moore graphs
possess an automorphism group
that acts transitively on the set of vertices of the graph.
Similarly, the majority of the other graphs discussed in this survey
have a large automorphism group with very few orbits.
These observations suggest that highly symmetric graphs
deserve a careful examination.

In the case of small cages the reason behind the usefulness of 
symmetric graphs may be due to the fact that small regular graphs are more 
likely to have a relatively large group of automorphisms, while
for larger instances of the cage problem,
this may be due to the fact that symmetric graphs are easier to construct.

An {\em automorphism} of a graph $G$ is a permutation $\varphi$
of the vertices of $G$ that preserves the structure of $G$, i.e.,
any two vertices, $u$ and $v$, are adjacent if and only if
$\varphi(u)$ is adjacent to $\varphi(v)$.  The set of all
automorphisms of $G$ forms a group, $Aut(G)$, under the operation of
composition.

In the following subsections, we review the class of
vertex-transitive graphs and its subclass of Cayley graphs.

\hypertarget{vt-sec}{}
\subsection{Vertex-Transitive Graphs}\label{vt-sec}
A group $G$ acting on a set $V$ is said to {\em act transitively}
on $V$ if for any $u,v \in V$, there exists an element $g \in G$
that maps $u$ to $v$.
A graph $G$ is {\em vertex-transitive} if $Aut(G)$, 
the automorphism group of $G$, acts transitively on the set of vertices
$V(G)$ (\cite{biggsbook}).
Thus, vertex-transitive graphs look the same
at each vertex, and all the vertices of such graphs lie on the 
same number of cycles of any particular length.
In particular, each vertex lies on a cycle of length $g$,
the girth of the graph.  In fact, the number of cycles of any fixed length
through 
any vertex $v$ must satisfy additional arithmetic properties related to 
the order of the graph, $|V(G)|$, (see, for example, \cite{jajmalmar}).
Looking at the other end of the cycle spectrum,
note that all but four of the known non-trivial vertex-transitive 
graphs are Hamiltonian; the four exceptions being the Petersen and 
Coxeter graph, and the two graphs obtained from these by replacing 
their vertices by triangles.

The existence of vertex-transitive graphs for any degree $k \geq 2$
and girth $g \geq 3$ has been proved using \hyperlink{voltref}{voltage graphs and lifts} 
in \cite{nedsko}, 
and similar results can be deduced from the paper of Ma\v caj, 
\v Sir\' a\v n and Ipolyiov\' a \cite{macsir&ipo}.

Of all the known constructions of vertex-transitive graphs, let us 
mention the most direct one.
For the purpose of simplification we restrict
ourselves to the case of finite groups acting on finite sets.

Let $\Gamma$ be {\em a permutation group acting transitively on a set} $V$ 
(i.e., $ \Gamma \leq Sym(V) $, the full symmetric group of all permutations 
of the set $V$), and let $ v^g $ denote the vertex resulting from the action
of $ g \in \Gamma $ on $ v \in V $. Then $\Gamma$ has a natural induced 
action on the Cartesian product $ V \times V $ defined by $ (u,v)^g = 
(u^g,v^g) $, for all $ (u,v) \in V \times V $ and $ g \in \Gamma $, and 
the $\Gamma$ orbits in $ V \times V $ are called the 
{\em orbitals} of $\Gamma$. 
For each orbital $\Delta$ of the action of $\Gamma$ on $V \times V$, 
there is a {\em paired orbital} $\Delta^* = \{ (v,u) \; | \; (u,v) \in
\Delta \} $. 

Let $\Omega$ be any set of orbitals of $\Gamma$ closed under taking paired 
orbitals, and let $E$ be the set of (unordered) pairs $ \{ u,v \} $ such 
that $ (u,v) $ belongs to $\Omega$. Then the graph $ G = (V,E) $ is called the 
{\em orbital graph} of $\Gamma$ (with respect to $\Omega$). It is easy to 
see that the orbital graph of any transitive permutation group is a 
vertex-transitive graph, and moreover, that any vertex-transitive graph 
$G = (V,E) $ is the orbital graph of any of its vertex-transitive automorphism 
groups $\Gamma \leq Aut(G)$ with $ \Omega = \{ (u,v)^g \; | \; 
\{ u,v \} \in E, g \in \Gamma \} $, i.e., the class of vertex-transitive 
graphs is the 
class of orbital graphs of transitive permutations groups (for more details 
see \cite{praeger}). 

Note in addition that an abstract group $\Gamma$ has a transitive permutation
representation on a set of size $n$ if and only if $\Gamma$ has a subgroup 
$\Lambda$ of index $n$; in which case $\Gamma$ can be thought of as acting on 
the (right) cosets of $\Lambda$ in $\Gamma$ via (right) multiplication
(\cite{biggsoldbook}). Hence, 
the class of (finite) vertex-transitive graphs is the 
class of orbital graphs of (finite) groups acting via left multiplication 
on the left cosets of their subgroups, and {\em every} vertex-transitive 
graph whose automorphism group contains $\Gamma$ acting transitively on 
its vertices can be obtained by choosing appropriate $\Lambda$ and $\Omega$.

Although vertex-transitive graphs constitute a significant part of the known
cages and record holders, it can be shown that their orders have to be (in at least
some cases) bigger than the Moore bound.
In addition to Biggs' Theorem~\ref{biggsvt}, which showed that the excess for
vertex-transitive graphs can be arbitrarily large, the paper
\cite{jajsir} contains additional improvements on the lower bounds
for vertex-transitive graphs of given degree and girth.

\begin{theorem}[\cite{jajsir}]
Let $G$ be a vertex-transitive graph of valency $k$ and girth $g=p^r>k$,
where $p$ is an odd prime and $r \geq 1$.
If $G$ is not a Moore graph (that is, $|V(G)| > M(k,g)$), and $g$ is relatively 
prime to all the integers in the union
\[ \bigcup_{0 \leq i \leq k} {\cal L}(k,g,i), \]
where $ {\cal L}(k,g,0) = \{ M(k,g)+1, M(k,g)+2, \ldots, M(k,g)+k \} $, and
$ {\cal L}(k,g,i) = $ \newline
$ \{ k(k-1)^{(g-1)/2} - ik, \; k(k-1)^{(g-1)/2} - ik+1,  
\ldots, \; k(k-1)^{(g-1)/2} - ik +i -1 \} $, $ i>0$,
\newline
then the order of $G$ is at least $M(k,g)+k+1$.
\end{theorem}

\hypertarget{cayref}{}
\subsection{Cayley Graphs} \label{cayref}
A vertex-transitive graph $G$ is Cayley if there exists an automorphism 
group $\Gamma$ of $G$ that {\em acts regularly} on $V(G)$; i.e., for each 
$u,v \in V(G)$, there exists {\em exactly one} automorphism 
$\varphi \in \Gamma$ such that $\varphi(u)=v$. 

Cayley graphs constitute a subclass of the class of vertex-transitive
graphs that have proved particularly useful in the construction of cages.
The following definition is the one used throughout our survey.

Let $\Gamma$ be an (abstract) finite group with a generating set $X$ that does
not contain the identity of $\Gamma$ and is closed under taking inverses,
$X=X^{-1}$ (no assumptions are made about the minimality of $X$).
The {\em Cayley graph} $C(\Gamma,X)$ is the regular
graph of degree $|X|$ 
that has $\Gamma$ for its set of vertices and whose adjacency is defined 
by making each vertex $g$ of the graph, $g \in \Gamma$, adjacent to all the 
vertices in the set $ g \cdot X = \{ g \cdot x \; | \; x \in X \} $.
Alternatively,
for any two vertices $g,h \in \Gamma$, $h$ is adjacent to $g$ 
if and only if $ g^{-1}h \in X $. Note that the fact that $X$ is closed 
under inverses makes the resulting graph undirected.

Besides being useful in cage construction,
Cayley graphs have also been useful in proofs.
The proof of the following result mentioned in the introduction
is a generalization of a proof due to Biggs \cite{biggsny}.
 
\begin{theorem}
Given any $k,g \geq 3$, there exists a $k$-regular graph $G$ with girth at
least $g$.
\end{theorem}
{\bf Proof.}
The graph we construct is a Cayley graph.

Let $k,g \geq 3$, $ r=\lfloor \frac{g}{2} \rfloor $, and $T_{k,r} $ denote the 
finite tree of radius $r$ with center $x$ in which all the vertices, whose
distance from $x$ is less than $r$, are of degree $k$; and the vertices at distance
$r$ from $x$ are leaves of degree $1$. Color the edges of $T_{r,k}$ by the $k$
colors $\{ 1,2,3, \ldots,k \} $ subject to the edge-coloring rule that no two 
adjacent edges are of the same color. For each color $i$, let $\alpha_i$ 
denote the involutory
permutation of the vertices of $ T_{k,r} $:
\[ \alpha_i(u) = v \mbox{ if and only if the edge } \{ u,v \} \mbox{ is colored by }
i. \]
Let $\Gamma = \left< \alpha_1, \alpha_2, \ldots , \alpha_k \right> $ be the 
finite permutation group generated by the involutions $ \alpha_i $, and take
$ X = \{  \alpha_1, \alpha_2, \ldots , \alpha_k \} $. We claim that the $k$-regular
graph
$ C(\Gamma,X) $ has girth at least $g$. First observe that any cycle of
length $s$ in $C(\Gamma,X)$ corresponds to a reduced word 
$ w(\alpha_1, \alpha_2, \ldots , \alpha_k) $ of length $s$ that is equal to
$1_{\Gamma}$, $ w(\alpha_1, \alpha_2, \ldots , \alpha_k) = 1_{\Gamma} $ 
(a word is reduced if no $\alpha_i$'s is immediately followed by itself).
Clearly, 
$ w(\alpha_1, \alpha_2, \ldots , \alpha_k) = 1_{\Gamma} $ implies  
$ w(\alpha_1, \alpha_2, \ldots , \alpha_k)(x) = x $, for all $x \in X$,
in the action of 
$\Gamma$ on the vertices of $T_{k,r}$.
Consider the effect of 
$ w(\alpha_1, \alpha_2, \ldots , \alpha_k) $ on $x$, a neighbor of $1_{\Gamma}$.   
Initially, each element of the word moves $x$ one step toward the leaves.
In order for the image of $x$ to return back to $x$, an additional $r+1$ elements
are required. Thus, any reduced word representing the identity must have 
length at least $2r+1$. Equivalently, the girth of $C(\Gamma,X)$ is 
at least $g$. \hfill $\square$
\medskip

Note that not all vertex-transitive graphs are Cayley. 
The Petersen graph is the smallest exception.
Thus, the constructions of vertex-transitive $(k,g)$-graphs referenced in
Section~\ref{vt-sec} do not imply the existence of $(k,g)$-Cayley graphs.
The existence of Cayley graphs for all pairs $(k,g)$ has first been proved in
\cite{jajsir}.

\begin{theorem}[\cite{jajsir}]
For every pair of parameters $k \geq 2,g \geq 3$, there exists a finite Cayley
graph $C(\Gamma,X)$ of valency $k$ and girth $g$.
\end{theorem}

In Table 7 below, we compare the orders of the smallest known
$(k,g)$-graphs,
the smallest
vertex-transitive $(k,g)$-graphs,
and the smallest Cayley $(k,g)$-graphs.
The column labels in Table 7 stand for the current lower bound (\emph{lb}),
the order of the current record $(3,g)$-graph (\emph{rec}),
the order of the the smallest vertex-transitive
$(3,g)$-graph (\emph{vt}), and the order of the smallest Cayley
$(3,g)$-graph (\emph{cay}).
It is worth emphasizing that in the cases of vertex-transitive and Cayley
graphs, the orders listed in the columns \emph{vt} and \emph{cay}
are not bounds, but rather exact values
\cite{potspi&ver}.
\medskip

\hypertarget{vttable}{}
\begin{center}
\begin{tabular}{|r||r|r|r|r|} \hline\hline
\multicolumn{1}{|c||}{\emph{girth}} &
\multicolumn{1}{c|}{\emph{lb}} &
\multicolumn{1}{c|}{\emph{rec}} &
\multicolumn{1}{c|}{\emph{vt}} &
\multicolumn{1}{c|}{\emph{cay}}  \\ \hline \hline
 5 & 10 & 10 & 10 & 50 \\
 6 & 14 & 14 & 14 & 14 \\
 7 & 24 & 24 & 26 & 30 \\
 8 & 30 & 30 & 30 & 42 \\
 9 & 58 & 58 & 60 & 60 \\
10 & 70 & 70 & 80 & 96 \\
11 & 112 & 112 & 192 & 192 \\
12 & 126 & 126 & 126 & 162 \\
13 & 202 & 272 & 272 & 272 \\
14 & 258 & 384 & 406 & 406 \\
15 & 512 & 620 & 620 & 864 \\
16 & 768 & 960 & 1008 & 1008 \\ \hline\hline
\end{tabular}
\end{center}

\vspace{3 mm}
\begin{center}
\noindent
{\bf Table 7. } Cubic vertex transitive and Cayley cages.
\end{center}
\medskip

\hypertarget{voltref}{}
\subsection{Voltage Graphs}
\label{voltref}
The voltage graph construction originally comes from topology.
Its main use in the context of graph theory has been primarily restricted to
topological graph theory where it was instrumental in such important achievements
as Ringel and Youngs' solution of the Heawood Map Coloring problem
\cite{ringelyoungs}.
Voltage graphs are a special case of graph covers,
distinguished by the existence of an automorphism group that acts
regularly on each of the fibers.
The main reason for the efficacy of voltage graphs in combinatorial constructions
lies in their flexibility with respect to the full symmetry spectrum starting from
highly symmetric graphs on one side and ending with graphs with trivial
automorphism groups on the other.

Informally, voltage graphs are lifts of
base graphs determined by an assignment of group elements to
oriented edges of the base graph.
A {\em base graph} is a finite 
digraph with possible loops and multiple edges. We denote 
its vertex, edge, and arc (oriented edge) sets by $V(G)$, $E(G)$,
and $D(G)$, respectively. Each edge $e \in E(G)$ is represented 
twice in $D(G)$ (once with each of the two possible orientations)
and if $e \in D(G)$, we denote the reverse arc by $e^{-1}$.

Given a finite group $\Gamma$, a {\em voltage assignment}
is a function $\alpha: D(G) \rightarrow \Gamma$ satisfying the 
property $\alpha(e^{-1}) = g^{-1}$ whenever $\alpha(e) = g$. 
The group $\Gamma$ is called the {\em voltage group}. 

Given a voltage assignment $\alpha: D(G) \rightarrow \Gamma$, 
the {\em lift} of $G$, often called the {\em derived graph} or
the {\em derived regular cover} of $G$, denoted by $G^{\alpha}$, 
is the graph whose vertex set is $V(G) \times \Gamma$ with two 
vertices $(u,g)$ and $(v,h)$ 
adjacent if and only if $uv \in E(G)$ and $g \cdot \alpha(uv) = h$.

We include two simple examples of the derived
graph construction.

First, consider the {\em dumbbell} graph depicted in Figure~\ref{petelift}.
with a voltage assignment chosen from $ Z_5 $. The derived 
graph in this example is the Petersen graph.

\begin{figure}[ht]
\centering
\includegraphics[width=5cm]{petelift.png}
\caption{The Petersen graph as a lift}\label{petelift}
\end{figure}

\hypertarget{theta}{}
Our second example, shown in Figure~\ref{heawoodlift},
gives rise to the Heawood graph. 
The base graph is a $\theta$-{\em graph} (dipole) with a voltage assignment from 
$Z_7$.

\begin{figure}[ht]
\centering
\includegraphics[width=5cm]{heawoodlift.png}
\caption{The Heawood graph as a lift}\label{heawoodlift}
\end{figure}

Another example of the use of voltage graphs in cage construction is in the
proof of Sachs' result concerning consecutive odd-even girths 
in Theorem~\ref{sachs-odd-even}.
Namely, using the voltage group ${\Bbb Z}_2$ and assigning the non-identity
voltage $1$
to all edges of a regular graph $G$ results in a lift of twice the 
order of $G$ with the property that all the odd-length cycles of $G$ are
lifted into cycles of doubled lengths while the lengths of the even-length
cycles remain unchanged. Hence,
\[ n(k,g+1) \leq 2 n(k,g) \]
for $g$ odd.

The following result shows that one can use the voltage graph construction
to increase the girth of a
base graph by an arbitrary multiple.

\begin{theorem}[\cite{girthlift}]
Let $G$ be a base graph of girth $g$, and $k>1$ be an integer.
Then there exists a voltage graph lift of $G$ of girth at least $kg$.
\end{theorem}

\section{Computer Methods}
\label{compref}
Computers have been used in the study of cages
since the 1960's.
O'Keefe and Wong
used them to complete
detailed case analyses \cite{okwong5,okwong10,okwong6,wong}.
More intensive use of computers followed
the introduction of McKay's {\it nauty}
package \cite{nauty}, which proved to be particularly
useful in work on lower bounds \cite{brimcksaa,mckmyr,emmn}.
Similarly, progress on upper bounds followed the development of
programs such as GAP \cite{gap},
which facilitated the use of large groups in Cayley and
voltage graph constructions.

\hypertarget{lowerbounds}{}
\subsection{Lower Bound Proofs and Isomorphism Checking}
Computational proofs that have established the correct
lower bounds for the orders of
some of the cages
were made possible by the ability to do fast isomorphism
testing \cite{nauty}.

This approach has been used to
establish the correct lower bounds for
$n(3,9)$ \cite{brimcksaa},
$n(3,11)$ \cite{mckmyr}, and $n(4,7)$ \cite{emmn}.
Such proofs are organized by
splitting the
problem into a large number of
subproblems, which can then be handled independently,
and the work can be done in parallel
on many different computers.

The computation can begin by selecting a root vertex and
constructing a rooted $k$-nary tree of radius $\frac{g-1}{2}$.
The actual computation proceeds in two phases.
First, all non-isomorphic
ways to add sets of $m$ edges
to the tree are determined
(for some experimentally
determined value of $m$).
This phase involves extensive isomorphism checking.
The second phase is the one that is more easily
distributed across a large number of computers.
Each of the isomorphism classes found in the first phase
becomes an independent starting point for an exhaustive
search to determine whether the desired graph can be completed.
Of all possible edges that could be added to the graph at this
point, those that would violate the degree or girth conditions
are eliminated.
The order in which the remaining edges are considered is then
determined by heuristics.

\subsection{Computer Searches}
The great majority of upper bounds presented in our tables were
obtained using extensive computer search techniques.
The methods differ by the level of symmetry assumed.

On one extreme, one can assume that the desired graph is Cayley.
Several investigators have developed fast methods that found small
\hyperlink{cayref}{Cayley graphs} of large girth \cite{conder,hafner2}.
However, most of the current record holders for degree $k \geq 3$ and girth
$g \geq 14$ were found by relaxing the Cayley graph symmetry requirement.
For example,
\hyperlink{bprtar}{Bray, Parker, and Rowley} \cite{brayetal} 
constructed their graphs by collapsing cycles in Cayley graphs.
All their resulting graphs are vertex-transitive.

Further relaxation of the symmetry requirements can be made by noting
that all Cayley graphs are \hyperlink{voltref}{voltage graphs}:
lifts of a one-vertex bouquet of cycles.
As one increases the order of the base graph and decreases the order of the
group, the symmetry tends to decrease (and ultimately one can think of
all graphs as voltage graphs with a trivial voltage group). Hence,
the voltage graph construction is a natural generalization of the
Cayley construction allowing one to fine-tune symmetry assumptions.
Instead of searching through the space of groups whose order $n$ equals the
order of the desired graph, one
can expand the search to include base graphs of order greater than one
and voltage groups of order less than $n$ \cite{exoo14,exoo16,exoo18}.

Ultimately, one can completely eliminate symmmetry assumptions.
The largest cases where this type of search has been successful in finding cages,
and perhaps the largest cases where it is feasible,
are $n(3,9) = 58$ \cite{brimcksaa}
and $n(4,7) = 67$ \cite{emmn}. 

\section{The Upper Bound of Erd\"{o}s} \label{erdproof}
The following is essentially a verbatim translation of the
Erd\H{o}s' original proof in German \cite{erdossachs},
subject to some notational
changes.

\begin{theorem}[\cite{erdossachs}]
For every $ k \geq 2 $, $ l \geq 3 $,
\begin{equation}\label{(1)}
n(k,g) \leq 4 \sum_{t=1}^{g-2}(k-1)^t 
\end{equation}
\end{theorem}

Note that for $ k=2 $ as well as $ g=3 $ the bound (\ref{(1)}) is sharp, and 
so from now on we will assume $ k>2 $ and $ g>3 $.
\medskip

In order to prove the upper bound, we prove the following slightly stronger
claim:
\medskip

{\em Let $ k \geq 2 $, $ g \geq 4 $, $ m \geq 2 \sum_{t=1}^{g-2} (k-1)^t $.
Then there exists a $k$-regular graph $G^{(2m)}$ of order $2m$ with the property
that all of its cycles are of length at least $g$.}
\medskip

We prove this theorem for a fixed $g$ using induction on $k$. For $k=2$, everything 
is trivial, $G^{(2m)}$ is simply the cycle of length $2m$ ($ 2m > g $ is clear).
Let us assume now that our theorem holds for $k-1$; we want to prove it for $k$.
From now on, let $G^{(n)}(k,g)$ denote a $k$-regular graph of girth $\geq g$ with 
exactly $n$ vertices. By our induction hypothesis, there exists a graph
$G^{(2m)}(k-1,g)$. Let $G^{(2m)}$ now be a graph with the following three properties:
\begin{description}
\item{(I)} $k-1 \leq v(x) \leq k $ for the degree $v(x)$ of all the $2m$ vertices
\item{(II)} all cycles have length at least $g$
\item{(III)} $G^{(2m)}$ has the maximal number of edges among all the graphs satisfying
(I) and (II). 
\end{description}
As $G^{(2m)}(k-1,g)$ satisfies (I) and (II), it is clear that $G^{(2m)}$ exists.
We intend to show that the degrees of all the vertices of $G^{(2m)}$ are exactly $k$,
hence $G^{(2m)}$ is $k$-regular, which will complete the proof.

First, we want to show that $G^{(2m)}$ contains at most one vertex of degree $ <k$.
Since this proof is not at all easy, let us first show that this result already
implies the $k$-regularity of $G^{(2m)}$. Because of (I), the exceptional vertex must
be of degree $k-1$. But that is impossible, due to the well-known fact that the number 
of vertices of odd degree must be even, and an even $k$ would force the existence of 
exactly one vertex of odd degree, while an odd $k$ would force the existence of 
exactly $2m-1$ such vertices; it therefore follows that all the vertices are of degree
$k$ and the proof of our theorem is completed.

Hence, it remains to prove that the existence of two vertices $x_1$
and $x_2$ in $G^{(2m)}$ of degree $ < k $ (i.e., of degree $k-1$) leads to a 
contradiction.
Let
$N(x_i,g-2)$ stands for the set of vertices in $G^{(2m)}$ whose distance from 
$x_i$ is at most $ g-2 $.
Then we claim:

\begin{lemma}\label{lemma1}
The set of all the vertices in $G^{(2m)}$ of degree less than  $k$ is 
contained in $ N(x_1,g-2) \cap N(x_2,g-2) $.
\end{lemma}

It is enough to show this for $N(x_1,g-2)$. If there existed an $ x \not \in 
N(x_1,g-2)$ of degree $<k$, the graph $G^{(2m)} + (x_1,x)$ 
(i.e., $G^{(2m)}$ with an added edge) would obviously satisfy conditions 
(I) and (II).
Property (I) follows because the degree of both $x_1$ and
$x$ is assumed to be less than $k$, and property (II) follows
because $ x \not \in N(x_1,g-2)$. 
This would however contradict the maximality property (III) of $G^{(2m)}$, 
and so Lemma~\ref{lemma1} is proved.

\begin{lemma}\label{lemma2}
Let $x$ be a vertex of $G^{(2m)}$ of degree $<k$. Then
\begin{equation}\label{(3)}
|N(x,r)| \leq \sum_{t=0}^r (k-1)^t.
\end{equation}
\end{lemma}

Since the degree of $x$ is smaller than $k$, (\ref{(3)}) follows for $r=1$.
The rest of the proof for $r>1$ follows from a simple induction on $r$ using 
the fact that the degree of all the vertices is at most $k$.

Combining Lemmata \ref{lemma1} and \ref{lemma2}, we obtain
\begin{equation}\label{(4)}
|N(x_1,g-2) \cup N(x_2,g-2)| \leq m,
\end{equation}
as it follows obviously from (\ref{(3)}) and Lemma \ref{lemma1} that 
\begin{eqnarray*}
 |N(x_1,g-2) \cup N(x_2,g-2)| = \\
=  |N(x_1,g-2)| +  |N(x_2,g-2)| - 
| N(x_1,g-2) \cap N(x_2,g-2) | \leq \\
\leq 2 \sum_{t=0}^{g-2} (k-1)^t - 2 \leq m 
\end{eqnarray*}
(because of Lemma \ref{lemma1} and because the degrees of $x_1$ and $x_2$ 
are smaller than $k$, 
$ | N(x_1,g-2) \cap N(x_2,g-2) | \geq 2 $). This proves (\ref{(4)}).

Now, let $ x_1, \ldots, x_p $ be the vertices contained in $ N(x_1,g-2) \cup 
N(x_2,g-2) $, and $ y_1, \ldots, y_{2m-p} $ be the remaining vertices of 
$G^{(2m)}$.
It follows from (\ref{(4)}) that
\begin{equation}\label{(5)}
2m-p \geq p 
\end{equation}
We want to show now that at least two of the $y_j$'s are joined by an edge.
First, because of Lemma \ref{lemma1}, the degree of all the vertices 
$y_j$ is $k$.  
If no two of the vertices $y_j$ were connected through an edge, 
there would have to
be $k(2m-p)$ edges connecting the $y_j$'s to the $x_i$'s. 
However, due to (\ref{(5)}) and
the fact that the degrees of all the $(2m-p)$ vertices $y_j$ is $k$, 
this would force the degrees
of $x_i$'s to be equal to $k$ as well; a contradiction.

We may assume without loss of generality that $G^{(2m)}$ contains the edge $y_1y_2$. 
Let us consider now the graph $(G^{(2m)} - y_1y_2 + x_1y_1 + x_2y_2) = 
\overline{G}^{(2m)} $ (the edges $x_1y_1$ and $x_2y_2$ do not 
belong to $G^{(2m)}$). 
We claim that $\overline{G}^{(2m)}$ satisfies (I) and (II).
Clearly, (I) holds true.
If $\overline{G}^{(2m)}$ contained a cycle of length 
less than $ g $,
this cycle would have to contain one (or both) of the edges 
$x_1y_1, x_2y_2$.
Because of the way the vertices $y_j$ were defined
\begin{eqnarray*}\label{(6)}
e(G^{(2m)}; x_1,y_1) \geq g-1 \\
e(G^{(2m)}; x_2,y_2) \geq g-1 \\
e(G^{(2m)}-(y_1,y_2); y_1,y_2) \geq g-1 
\end{eqnarray*}
where $e(G^{(2m)};x_i,y_i)$ stands for the distance between $x_i$ and $y_i$ 
in $G^{(2m)}$, and 
the last inequality follows from the fact that $G^{(2m)}$ does 
not contain cycles of length less than $g$. 

It follows easily from these inequalities that $\overline{G}^{(2m)}$ 
satisfies (II).
That, however, contradicts (III), as $\overline{G}^{(2m)}$ has more edges 
than $G^{(2m)}$. 

Hence, $G^{(2m)}$ can contain at most one vertex of degree $<k$, and that 
completes the proof of Theorem 2.

\addcontentsline{toc}{section}{References}
\begin{thebibliography}{99}

\bibitem{aablgirth5}
M. Abreu, G. Araujo-Pardo, C. Balbuena, and D. Labbate,
Families of small regular graphs of girth 5,
Discrete Math. 312 (2012) 2832-2842.

\bibitem{abreu}
M. Abreu, M.Funk, D. Labbate, and V. Napolitano,
On (minimal) regular graphs of girth 6,
Australas. J. Combin. 35 (2006) 119-132.

\bibitem{araujo}
G. Araujo-Pardo,
On upper bounds of odd girth cages,
Discrete Math. 310 (2010) 1622-1626.

\bibitem{arabal2}
G. Araujo-Pardo and C. Balbuena,
Constructions of small regular bipartite graphs of girth 6,
Networks 57 (2011) 121-127.

\bibitem{arabalheg}
G. Araujo-Pardo, C. Balbuena and H\'{e}ger,
Finding small regular graphs of girths $6$, $8$ and $12$ as subgraphs of cages,
Discrete Math. 310 (2010) 1301-1306.

\bibitem{araujoieee}
G. Araujo-Pardo and J. Montellano-Ballesteros,
Cages: constructions and new upper bounds.
Proceedings of the 8th International IEEE Symposium on
Parallel Architectures, Algorithms and Networks.

\bibitem{araujoetal}
G. Araujo, D. Gonz\'{a}lez,
J. Montellano-Ballesteros and O. Serra,
On upper bounds and connectivity of cages,
Australas. J. Combin. 38 (2007) 221-228.

\bibitem{asc}
M. Aschbacher, 
The non-existence of rank three permutation group of degree of 3250 and 
subdegree 57, 
J. Algebra 19 (1971) 538-540.

\bibitem{baker} 
R. D. Baker, An elliptic semiplane,
J. Combin. Theory Ser. A 25 (1978) 193-195.

\bibitem{balaban}
A. T. Balaban,
Trivalent graphs of girth nine and eleven, and relationships among cages,
Rev. Roum. Math. Pures et Appl. 18 (1973) 1033-1043.

\bibitem{balabanjct}
A. T. Balaban,
A trivalent graph of girth ten,
J. Combin. Theory Ser. B 12 (1972) 1-5.

\bibitem{balgonmon}
C. Balbuena, D. Gonz\' alez-Moreno and J. Montellano-Ballesteros,
A note on the upper bound and girth pairs of $(k;g)$-cages,
Discrete Applied Math. 161 (2013) 853-857.

\bibitem{balbuena8}
C. Balbuena,
A method for obtaining small regular bipartite graphs of girth 8,
DMTCS 11 (2009) 33-46.

\bibitem{banito}
E. Bannai and T. Ito,
On finite Moore graphs,
J. Fac. Sci. Tokyo, Sect. 1A, 20 (1973) 191-208.

\bibitem{Ban&Ito}
E. Bannai and T. Ito,
Regular graphs with excess one,
Discrete Math. 37 (1981) 147-158.

\bibitem{benson}
C.T. Benson,
Minimal regular graphs of girth eight and twelve,
Canad. J. Math. 18 (1966) 1091-1094.

\bibitem{bensonlosey}
C.T. Benson and N. E. Losey,
On a graph of Hoffman and Singleton.
J. Combin. Theory Ser. B 11 (1971) 67-79.

\bibitem{biggsoldbook}
N. Biggs,
Finite groups of automorphisms,
London Mathematical Society Lecture Note Series, 6,
Cambridge University Press, London, 1971.

\bibitem{big82}
N.L. Biggs,
Excess in vertex-transitive graphs,
Bull. London Math. Soc. 14 (1982) 52-54.

\bibitem{biggsresid}
N.L. Biggs,
Girth and residual finiteness,
Combinatorica 8 (1988) 307-312.

\bibitem{biggsny}
N.L. Biggs,
Cubic graphs with large girth,
Combinatorial Mathematics: Proceedings of the Third International Conference,
Annals of the New York Academy of Sciences 555 (1989) 56-62.

\bibitem{biggsbook}
N.L. Biggs, 
Algebraic Graph Theory (2nd Ed.), Cambridge University Press, 1993.

\bibitem{biggssurvey}
N.L. Biggs,
Constructions for cubic graphs of large girth,
Electron. J. Combin. 5 (1998) A1.

\bibitem{big&bos}
N.L. Biggs and A.G. Boshier, 
Note on the girth of Ramanujan graphs,
J.Combin. Theory Ser. B 49 (1990) 190-194.

\bibitem{biggshoare}
N.L. Biggs and M.J. Hoare,
A trivalent graph with 58 vertices and girth 9,
Discrete Math. 30 (1980) 299-301.

\bibitem{sextet}
N.L. Biggs and M.J. Hoare,
The sextet construction for cubic graphs,
Combinatorica 3 (1983) 153-165.

\bibitem{Big&Ito}
N.L. Biggs and T.Ito,
Graphs with even girth and small excess,
Math. Proc. Cam. Philos. Soc. 88 (1980) 1-10.

\bibitem{bobjaj&pis}
M. Boben, R. Jajcay, and T. Pisanski,
Explicit constructions of graphs with prescribed and prohibited 
degrees and cycle lengths, submitted for publication.

\bibitem{bose}
R. C. Bose,
An affine analogue of Singer's theorem,
J. Indian Math. Soc. 6 (1942) 1-15.

\bibitem{brayetal}
J. Bray, C. Parker and P. Rowley,
Cayley type graphs and cubic graphs of large girth,
Discrete Math.  214 (2000) 113-121.

\bibitem{french}
A. Bretto and L. Gillibert,
Some upper bounds for the (p,6) and (p,8)-cage,
preprint.

\bibitem{brimcksaa}
G. Brinkmann, B. D. McKay and C. Saager,
The smallest cubic graphs of girth nine,
Combin. Probab. Comput. 5 (1995) 1-13.

\bibitem{brurys}
R. H. Bruck and H. J. Ryser,
The nonexistence of certain finite projective planes,
Canad. J. Math 1 (1949) 88-93.

\bibitem{drg}
A. E. Brouwer, A. M. Cohen and A. Newmeier,
Distance Regular Graphs, 
Springer, Berlin, 1989.

\bibitem{brownham}
W. G. Brown,
On Hamiltonian regular graphs of girth $6$,
J. London Math. Soc. 42 (1967) 514-520.

\bibitem{brown}
W. G. Brown, On the non-existence of a type of regular graphs of girth $5$,
Canad. J. Math. 19 (1967) 644-648.

\bibitem{cameron}
Peter J. Cameron,
Permutation Groups,
Cambridge University Press, 1999.

\bibitem{chandran}
L. S. Chandran,
A high girth graph construction,
SIAM J. Discrete Math. 16 (2003) 366-370.

\bibitem{conder}
M. Conder,
Small trivalent graphs of large girth,
University of Auckland Centre for Discrete Mathematics and
Theoretical Computer Science
Research Report Series, No. 42, 1997.

\bibitem{girthsolv}
M. Conder, G. Exoo and R. Jajcay,
On the limitations of the use of solvable groups in
Cayley graph cage constructions,
Europ. J. Combin. 31 (2010) 1819-1828.

\bibitem{dam}
R. M. Damerell,
On Moore graphs,
Proc. Cambridge Phil. Soc. 74 (1973) 227-236.

\bibitem{dusart}
P. Dusart,
The $k^{th}$ prime is greater than $k(\ln(k) + \ln(\ln(k)) - 1)$,
Math. Comp. 68 (1999) 411-415.

\bibitem{ellbut}
J. E. H. Elliot and A. T. Butson,
Relative difference sets,
Illinois J. Math. 10 (1966) 517-531.

\bibitem{erdossachs}
P. Erd\H{o}s and H. Sachs,
Regul\" are Graphen gegebener Taillenweite mit minimaler Knotenzahl,
Wiss. Z. Uni. Halle (Math. Nat.) 12 (1963) 251-257.

\bibitem{erosch}
L. Eroh and A. Schwenk,
Cages of girth 5 and 7,
Congr. Numer. 138 (1999) 157-173.

\bibitem{exoo14}
G. Exoo,
A small trivalent graph of girth 14,
Electron. J. Combin. 9 (2002) N3.

\bibitem{exoo16}
G. Exoo,
Voltage graphs, group presentations and cages,
Electron. J. Combin.  11 (1) (2004) N2.

\bibitem{exoo18}
G. Exoo,
New small trivalent graphs for girths $17$, $18$ and $20$,
preprint.

\bibitem{girthlift}
G. Exoo and R. Jajcay,
On the girth of voltage graph lifts,
Europ. J. Combin. 32 (2011) 554-562.

\bibitem{emmn}
G. Exoo, B. D. McKay, W. Myrvold and J. Nadon,
Computational determination of $(3,11)$- and $(4,7)$-cages,
Journal of Discrete Algorithms 9 (2011) 166-169.

\hypertarget{exooweb}{}
\bibitem{exooweb}
G. Exoo,
Regular graphs of given degree and girth.\\
\verb+http://ginger.indstate.edu/ge/CAGES+

\bibitem{feihig}
W. Feit and G. Higman,
The non-existence of certain generalized polygons,
J. Algebra 1 (1964) 114-131.

\bibitem{fu}
H. Fu, K. Huang and C. Rodger,
Connectivity of cages,
J. Graph Theory 24 (1997) 187-191.

\bibitem{furser}
Z. F\" uredi, F. Lazebnik, \' A. Seress, V. A. Ustimenko, A. J. Woldar,
Graphs of prescribed girth and bi-degree,
J. Combin. Theory Ser. B
64 (2) (1995) 228-239. 

\hypertarget{gacs}{}
\bibitem{gacs}
A. G\' acs and T. H\' eger,
On geometric constructions of $(k,g)$-graphs,
Contributions to Discrete Mathematics 3 (2008) 63-80.

\bibitem{gap}
The GAP~Group, GAP -- Groups, Algorithms, and Programming, 
Version 4.4.9, 2006,
\verb+http://www.gap-system.org+

\bibitem{handbook}
R.L. Graham, M. Gr\" otschel, L. Lov\' asz,
Handbook of Combinatorics, Vol. 1-2,
MIT Press, 1995.

\bibitem{hafner}
P.R. Hafner,
On the graphs of Hoffman-Singleton and Higman-Sims,
Electron. J. Combin. 11 (2004) R77.

\bibitem{hafner2}
P.R. Hafner,
Large Cayley graphs and digraphs with small degree and diameter,
University of Auckland Centre for Discrete Mathematics and
Theoretical Computer Science
Research Report Series, No. 5, 1995.

\bibitem{harwri} G.H. Hardy and E.M. Wright, An Introduction to the 
Theory of Numbers, 5-th ed., Clarendon, Oxford XVI (1979).

\bibitem{hirsch}
J.W.P. Hirschfield,
Projective Geometries over Finite Fields, 2nd ed.,
Clarendon, Oxford (1998).

\bibitem{hexagon}
M. Hoare.
Triplets and hexagons,
Graphs Combin. 9 (1993) 225 - 233.

\bibitem{hoffsing}
A.J. Hoffman and R. R. Singleton,
On Moore graphs with diameters 2 and 3,
IBM J. Res. Develop. 4 (1960) 497-504.

\bibitem{petersenbook}
D. A. Holton and J. Sheehan,
The Petersen Graph,
Australian Mathematical Society Lecture Series 7,
Cambridge University Press, 1993.

\bibitem{imrich}
W. Imrich, Explicit constructions of graphs without small cycles,
Combinatorica 2 (1984) 53-59.

\bibitem{jajmalmar}
R. Jajcay, A. Malni\v c, and D. Maru\v si\v c, 
On the number of closed walks in vertex-transitive graphs, 
Discrete Math. 307, no. 3-5, 484-493 (2007).

\bibitem{jajsir}
R. Jajcay and J. \v Sir\' a\v n, 
Small vertex-transitive graphs of given degree and girth,
Ars Mathematica Contemporanea 4 (2011) 375-384.

\bibitem{jajjaj}
T. Jajcayov\' a and R. Jajcay,
On the contributions of D. M. Mesner,
Bull. Inst. Combin. Appl. 36 (2002) 46-52.

\bibitem{james}
L.O. James,
A combinatorial proof that the Moore (7,2) graph is unique,
Utilitas Math. 5 (1974) 79-84.

\bibitem{jorgensen}
L. K. J{\o}rgensen,
Girth 5 graphs from relative difference sets,
Discrete Math. 293 (2005) 177-184.

\bibitem{karteszi}
F. K\'{a}rteszi,
Piani finiti ciclici come risoluzioni di un certo problema di minimo,
Boll. Un. Mat. Ital. (3) 15 (1960) 522-528.

\bibitem{kovacs} 
P. Kov\' acs, The nonexistence of certain regular graphs of girth 5,
J. Combin. Theory Ser. B 30 (1981) 282-284.

\bibitem{lam}
C. W. H. Lam, L. Thiel and S. Swiercz,
The nonexistence of finite projective planes of order 10,
Canad. J. Math. 41 (1991) 1117-1123.

\bibitem{lazustwol}
F. Lazebnik, V.A. Ustimenko, and A.J. Woldar,
A new series of dense graphs of high girth,
Bull. Amer. Math. Soc. 32 (1995) 73-79.

\bibitem{lazustwol2}
F. Lazebnik, V.A. Ustimenko, and A.J. Woldar,
New upper bounds on the order of cages,
Electron. J. Combin. 4(2) (1997) R13.

\bibitem{lubphisar}
A. Lubotzky, R. Phillips, and R. Sarnak,
Ramanujan graphs,
Combinatorica 8 (1988) 261-277.

\bibitem{macsir}
M. Ma\v caj and J. \v Sir\' a\v n, 
Search for properties of the missing Moore graph,
Linear Algebra and its Applications 432 (2010) 2381-2398.

\bibitem{macsir&ipo}
M. Ma\v caj, J. \v Sir\' a\v n, and M. Ipolyiov\' a, 
Injectivity radius of representations of triangle groups and planar width 
of regular hypermaps,
Ars Math. Contemp. 1, No. 2, (2008) 223-241.

\bibitem{makpad}
A. Makhnev and D.V. Paduchikh,
On automorphisms of the Aschbacher graph,
Algebra Logika 40 (2001) 125-134.

\bibitem{margulis}
G.A. Margulis, 
Explicit constructions of graphs without short cycles and low density codes, 
Combinatorica 2 (1982) 71-78. 

\bibitem{mcgee}
W.F. McGee,
A minimal cubic graph of girth seven,
Canad. Math. Bull. 3 (1960) 149-152.

\bibitem{nauty}
B.D. McKay, nauty Users Guide, Version 2.0.

\bibitem{greechie}
B.D. McKay, N.D. Megill and M. Pavi\v ci\' c,
Algorithms for Greechie diagrams,
Intl. J. Theoretical Physics 39 (2000) 2381-2406.

\bibitem{mckmyr}
B.D. McKay, W. Myrvold and J. Nadon,
Fast backtracking principles applied to find new cages,
9th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1998, 188-191.

\hypertarget{mckpc}{}
\bibitem{mckpc}
B.D. McKay, personal communication.

\bibitem{mesner}
D.M. Mesner,
An Investigation of Certain Combinatorial Properties of
Partially Balanced Incomplete Block Experimental Designs and
Association Schemes with a Detailed Study of Designs of Latin
Squares and Related Types,
Ph.D. Dissertation, Michigan State University, 1956.

\bibitem{milsir} 
M. Miller and J. \v Sir\' a\v n, Moore graphs and beyond: 
A survey of the degree/diameter problem, 
Electron. J. Combin., Dynamic Survey 14, 
December 2005.

\bibitem{nedsko}
R. Nedela and M. \v Skoviera, 
Regular maps on surfaces with large planar width, 
European J. Combin. 22 (2001) 243-261.

\bibitem{okwong5}
M. O'Keefe and P.K. Wong,
A smallest graph of girth 5 and valency 6,
J. Combin. Theory  Ser. B 26 (1979) 145-149.

\bibitem{okwong6}
M. O'Keefe and P.K. Wong,
The smallest graph of girth 6 and valency 7,
J. Graph Theory 5 (1981) 79-85.

\bibitem{okwong10}
M. O'Keefe and P.K. Wong,
A smallest graph of girth 10 and valency 3,
J. Combin. Theory Ser. B 29 (1980) 91-105.

\bibitem{okwongg5}
M. O'Keefe and P.K. Wong,
On certain regular graphs of girth 5,
Int. J. Math. and Math. Sci., 7 (1984) 785-791.

\bibitem{parsons}
T. Parsons,
Graphs from projective planes,
Aequationes Math. 14 (1976) 167-189.

\bibitem{petersen}
J. Petersen, Sur le th\' eor\` eme de Tait,
L'Interm\' ediaire des Math\' ematiciens 5 (1898) 225-227.

\bibitem{potspi&ver}
P. Poto\v cnik, P. Spiga and G. Verret,
Cubic vertex-transitive graphs on up to 1280 vertices,
J. Symbolic Comp. 50 (2013) 465-477.
 
\bibitem{praeger}
C. Praeger, C. Li, and A. Niemeyer,
Finite transitive permutation groups and finite vertex-transitive graphs,
Graph symmetry (Montreal, PQ, 1996),
NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci.,
497 (1997) 277-318.

\bibitem{reivadwig}
O. Reingold, S. Vadhan, and A. Wigderson,
Entropy waves, the zig-zag graph product, and new constant-degree expanders,
Annals of Mathematics 155 (1) (2002) 157-187.

\bibitem{ringelyoungs}
G. Ringel and J.W.T. Youngs,
Solution of the Heawood map-coloring problem,
Proc. Natl. Acad. Sci. USA 60 (1968) 438-445.

\bibitem{robertson}
N. Robertson,
The smallest graph of girth 5 and valency 4,
Bull. Amer. Math. Soc. 70 (1964) 824-825. 

\hypertarget{royle}{}
\bibitem{royle}
G. Royle,
Cubic Cages.\\
\verb+http://www.cs.uwa.edu.au/~gordon/cages+

\bibitem{sachs}
H. Sachs,
Regular graphs with given girth and restricted circuits,
J. London Math. Soc. 38 (1963) 423-429.

\bibitem{sauer}
N. Sauer,
Extremaleigenschaften regul\" arer Graphen gegebener Taillenweite,
I and II, Sitzungsberichte \" Osterreich. Akad. Wiss. Math. Natur. Kl.,
S-B II, 176 (1967) 9-25; 176 (1967) 27-43.

\bibitem{schwenk}
A. Schwenk,
Construction of a small regular graph of girth 5 and degree 19,
conference presentation given at Normal, IL, U.S.A., April 18, 2008.

\bibitem{shrsan}
M.S. Shrikhande and S.S. Sane,
Quasi-symmetric designs,
London Math. Soc. Lecture Notes Series 164,
Cambridge University Press, 1991.

\bibitem{tits1}
J. Tits,
Sur la trialit\' e et certains groupes qui s'en d\' eduisent,
Publ. Math. I.H.E.S.
Paris 2 (1959) 14-60.

\bibitem{tits2}
J. Tits,
Th\' eor\` eme de Bruhat et sous-groupes paraboliques,
Comptes Rendus Acad. Sci.
Paris 254 (1962) 2910-2912.

\bibitem{tutte}
W.T. Tutte,
A family of cubical graphs,
Proc. Cambridge Philos. Soc. 43 (1947) 459-474.

\bibitem{tuttebook}
W.T. Tutte,
Connectivity in graphs.
University of Toronto Press, 1966.

\bibitem{vanwil}
J.H. van Lint and R.M. Wilson,
A Course in Combinatorics,
2nd Ed., Cambridge University Press, 2001.

\bibitem{wang}
P. Wang,
An upper bound for the (n,5)-cages,
Ars Combin. 47 (1997) 121-128.

\bibitem{wegner}
G. Wegner,
A smallest graph of girth 5 and valency 5,
J. Combin. Theory Ser. B 14 (1973) 203-208.

\bibitem{weiss}
A.I. Weiss, Girth of bipartite sextet graphs,
Combinatorica 4 (1984) 241-245.

\bibitem{wong}
P.K. Wong,
On the uniqueness of the smallest graphs of girth 5 and valency 6,
J. Graph Theory 3 (1978) 407-409.

\bibitem{wongsurvey}
P.K. Wong,
Cages - a survey,
J. Graph Theory 6 (1982) 1-22. 

\bibitem{wong310}
P.K. Wong,
On the smallest graphs of girth 10 and valency 3,
Discrete Math. 43 (1983) 119-124.

\hypertarget{wong11}{}
\bibitem{wong11}
P.K. Wong,
A regular graph of girth 6 and valency 11,
Int. J. Math. Math. Sci. 9 (1986) 561-565.

\end{thebibliography}

\end{document}

