%corrected nov.22, 1996
%This is a plain TeX file.
%
\magnification=1200
\vsize=8truein
\hsize=6truein
\hoffset=.2truein
\parskip=10pt plus1pt minus.5pt
\baselineskip=12pt
\lineskip=1pt
\lineskiplimit=0pt
%\baselineskip=14pt
\def \bull{\vrule height 1.5ex width 1.4ex depth -.1ex }
\font\ninerm=cmr9
\font\nineit=cmti9
\font\smcp=cmcsc8
\headline={\ifnum\pageno>1 {\smcp the electronic journal of 
combinatorics 4 (no. 2) (1997) , \#R13\hfill\folio} \fi}
\bigskip
\centerline{\bf NEW UPPER BOUNDS ON THE ORDER OF CAGES%
\footnote{$^1$}
{\baselineskip=10pt
{\sevenrm This research was supported by
NSF grants DMS-9115473 and DMS-9622091. 
 A.J. Woldar was additionally supported by a Villanova
University Faculty Research Grant.
V.A. Ustimenko was additionally supported in part 
by INTAS-93-2530 and INTAS-94-3420.
F. Lazebnik was additionally supported by 
a University of Delaware Research Award.
}}}
\bigskip 
\centerline{F. LAZEBNIK}
\centerline{{\it Department of Mathematical Sciences}}
\centerline{{\it University of Delaware, Newark, DE 19716, 
USA; fellaz@math.udel.edu}}
\medskip
\centerline{V. A. USTIMENKO}
\centerline{{\it Department of Mathematics and Mechanics}}
\centerline{{\it University of Kiev, Kiev 252127, 
Ukraine; vau@trion.kiev.ua }}
\medskip
%\centerline{and}\medskip
\centerline{A. J. WOLDAR}
\centerline{{\it Department  of Mathematical Sciences}}
\centerline{{\it Villanova University, Villanova,
 PA 19085, USA; woldar@ucis.vill.edu}}
\bigskip
\centerline{Submitted: August 1, 1996;  Accepted: November 21, 1996.}
\bigskip
\centerline{\sl Dedicated to Herbert S.~Wilf 
on the occasion of his 65$^{th}$ birthday}
\bigskip
\medskip
\centerline{{\bf Abstract}}
\medskip
\begingroup
\baselineskip=10pt
{\parindent =12pt \narrower\narrower\narrower
{\sevenrm
Let $\scriptstyle{
k\ge 2}$ and $
\scriptstyle{g\ge3}$ be integers.
A $
\scriptstyle{(k,g)}$-graph is a $
\scriptstyle{k}$-regular graph
with girth 
(length of a smallest cycle) 
exactly $
\scriptstyle{g}$. 
A $
\scriptstyle{(k,g)}$-cage is a
$
\scriptstyle{(k,g)}$-graph of minimum order. 
Let $
\scriptstyle{v(k,g)}$ be the order of a 
$
\scriptstyle{(k,g)}$-cage.
The problem of determining $
\scriptstyle{v(k,g)}$ is unsolved for
most pairs $
\scriptstyle{(k,g)}$ and is extremely hard in the general
case.
It is easy to establish
the following  lower bounds for $
\scriptstyle{v(k,g)}$:
$
\scriptstyle{v(k,g)\ge} {{k(k-1)^{(g-1)/2}-2}\over {k-2}}$ 
for  $
\scriptstyle{g}$ odd,
and $
\scriptstyle{v(k,g)\ge}   { {2(k-1)^{g/2}-2}\over {k-2}}$ 
for $
\scriptstyle{g}$ even.
The best known  upper bounds
are roughly the squares of the lower bounds.
In this paper we establish general upper bounds on 
$
\scriptstyle{v(k,g)}$ which are
roughly the 3/2 power of the lower bounds,
and we provide explicit constructions for such 
$
\scriptstyle{(k,g)}$-graphs.

}\par}
\endgroup
\medskip
\noindent Mathematical Reviews Subject Numbers: 05C35, 05C38. Secondary: 05D99.
\bigskip
 
\noindent{\bf 1. Introduction}
\bigskip
All graphs in this paper are assumed to be simple (undirected, no loops, 
no multiple edges). 
Let $k\ge 2$ and $g\ge3$ be integers.
A $(k,g)$-graph is a $k$-regular graph
with girth (length of a smallest cycle) 
exactly $g$. A $(k,g)$-{\it cage} is a
$(k,g)$-graph of minimum order.
The problem of determining the order
$v(k,g)$ of a $(k,g)$-cage is unsolved for
most pairs $(k,g)$ and is extremely hard in the general
case.
By counting the number of vertices in the breadth-first-search tree of 
a $(k,g)$-graph, one easily establishes
the following  lower bounds for $v(k,g)$:
$$ v(k,g)\ge \cases{{{k(k-1)^{(g-1)/2}-2}\over {k-2}} &for  $g$ odd,\cr
			 { {2(k-1)^{g/2}-2}\over {k-2}}        
&for $g$ even.\cr}$$
Graphs whose orders achieve these lower bounds are very special
and possess many  
remarkable  properties.  Though there is no complete agreement on 
terminology, they are often 
referred to as ``Moore graphs'' when $g$ is odd, and  
``regular generalized polygons'' when $g$ is even. 
For references on cages, see Wong [23], Section 6.9 of 
Brouwer, Cohen and Neumaier [6],
Chapter 23 of Biggs [2], and Chapter 6 of Holton 
and Sheehan [8].  For a  survey of  
results on  cubic  cages ($k=3$) with girth at most $20$, 
see Royle [18]. 


Finding upper bounds
for $v(k,g)$ is a far more difficult affair; indeed,
even the fact
that $v(k,g)$ is finite is nontrivial to prove.
This was settled by Sachs [19] who
showed by explicit construction 
that $(k,g)$-graphs of finite
order exist. In the same year, Erd\H os and Sachs  [7] gave,
without explicit construction,
a much smaller general upper bound on
$v(k,g)$. (As was pointed by  Alon in [1, p.~1752], although
 their proof does supply a 
polynomial time algorithm for constructing graphs which 
provide the upper bound, 
their graphs are not really explicit in the sense that
 it is not clear 
how to decide efficiently whether or not two 
prescribed vertices of such a 
graph are adjacent.)
Their result was later improved, though slightly,
by Walther [21], [22] and by Sauer [20]. The following upper bounds
are due to Sauer [20]:
$$ v(k,g)\le \cases{2(k-1)^{g-2} &for $g$ odd and  $k\ge 4$, and \cr                          
			   4(k-1)^{g-3}  &for $g$ even and $k\ge 4$.
 \cr }\eqno (1)$$
Note that these upper bounds
are roughly the squares of the previously indicated lower bounds.

In this paper we establish general upper bounds on $v(k,g)$ which are
roughly the 3/2 power of the lower bounds,
and we provide explicit constructions for such $(k,g)$-graphs. 
The main results are described 
below.\hfil\eject
%\medskip
\noindent{\bf Theorem A.} {\it 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
$$v(k,g)\le 2kq^{{3\over 4}g - a}, \eqno (2)$$
 where $a = 4$, $11/4$, $7/2$, $13/4$ for
$g\equiv  0, 1, 2, 3\;{\rm mod\;} 4$,  respectively.}
\medskip
The upper bounds in (2) are better the ones provided in (1) 
for all $k\ge 5$ and $g\ge 5$. \break
\noindent For $k\ge t\ge 3$ and $q\equiv 1\; {\rm mod\;}  t$,  
$(k, 2t)$-graphs 
of orders at least as large as the upper bound in (2) were 
constructed in [9] by F\" uredi, 
Seress, and the authors.  The fact that the orders of
these constructions actually meet the upper bound in (2) for 
$q$ odd follows from [13]. The constructions we introduce 
in this paper are independent of the relative magnitudes of $k$ 
and $g$.
\medskip
 
\noindent{\bf Constructions.} {\it 
For all $k\ge 3$ and 
$g\ge 6$, $g$ even, we explicitly 
construct a 
$(k,g)$-graph of order
$$g\left(1+(k-2)kq^{g-5 - \lfloor {{g-3}\over 4}\rfloor }\right); \eqno (3)$$
for all $k\ge 3$ and $g\ge 5$, $g$ odd, we explicitly construct a 
$(k,g)$-graph of order
$$(g+1)\left(1+(k-2)kq^{g-4 - \lfloor {{g-2}\over 4}\rfloor}\right).
\eqno (4)$$  
In either case, $q$ is the smallest odd prime power 
for which $k\le q$.}

Though the upper bounds on $v(k,g)$
provided by these constructions are not as good as 
the ones given in Theorem A,
they are better than the bounds in (1) for all $k\ge 7$ and 
$g\ge 11$ when $g$ is odd, and $g\ge 8$ when $g$ is even.
With some additional restrictions on $k$ and $g$ these 
constructive upper bounds
can be improved still further. 

 
By Chebyshev's Theorem, for a fixed integer $k\ge 3$ there 
is always a prime between $k$ and $2k-2$. For any $\epsilon > 0$ 
and $k\ge k_0(\epsilon)$, this interval can be narrowed to 
$[k, k+  k^{{3\over 5} + \epsilon}]$, see [17, p.~131]. 
Thus the upper bounds from (2), (3), and (4) are roughly the 
3/2 power of the indicated lower bounds. \hfil\eject


%\bigskip\bigskip
\noindent{\bf 2. Preliminary Results and Proof of Theorem A} 

The possibility of improving the upper bounds in (1)  
for  $(k,g)\in
A\times B$, where
both $A$ and $B$ are certain infinite subsets of positive 
integers, became 
apparent after the discoveries of certain special infinite 
families of graphs 
which we describe below (see F1, F2 and F3).

For a fixed integer $k\ge 3$, let $\{G_i\}_{i\ge1}$ be a 
family of $k$-regular
graphs of increasing order $v_i$. Let $g_i$ denote the 
girth of $G_i$.
The family  $\{G_i\}$ is called a {\it family of graphs with 
large girth} if
$$g_i \ge \gamma\log _{k-1}(v_i)$$
for some positive constant $\gamma$ and all $i\ge 1$. The lower 
bound for $v(k,g)$ shows  that 
$\gamma\le 2$, but no infinite family has been found for 
which $\gamma = 2$.

\noindent{\bf F1.}  Margulis [16] and, independently, 
 Lubotzky, Phillips and Sarnak [15]
came up  with similar examples of graphs with $\gamma \ge 
 4/3$ and arbitrary
large valency (they turned out to be so--called Ramanujan graphs). 
These are Cayley graphs of
the group $P\!G\!L_2(Z_q)$ with respect to a set of $p+1$ 
generators, where
$p$ and $q$ are distinct
primes, each congruent to $1$ mod $4$, with the Legendre symbol
${p\overwithdelims() q} = -1$. Denoted by $X^{p,q}$, 
they are $(p+1)$-regular bipartite graphs of order 
$q(q^2 - 1)$.  Margulis [16] and, independently,  
Biggs and Boshier [3] showed that the asymptotic
 value of $\gamma$ for the graphs $X^{p,q}$ is exactly 
$4/3$. Moreover, in both papers an explicit formula 
for the girth $g(X^{p,q})$ of $X^{p,q}$ was found. 
To state their results (formulae (5), below) we first need 
the following definition.

Call an integer {\it good} if it is not of the form 
$4^{\alpha}(8\beta +7)$ for any nonnegative integers 
$\alpha, \beta$.  By a theorem of Legendre, good numbers
are precisely those which are representable as sums of 
three squares. Then 

$$ g(X^{p,q}) = \cases{2\lceil 2\log _p{q}  \rceil &if  
$p^{\lceil 2\log _p{q}  \rceil} - q^2$ 
is good,  \cr                          
2\lceil 2\log _p{q} + \log _p{2} \rceil  
&otherwise. \cr } \eqno (5)$$

\noindent{\bf F2.}  In [10], Lazebnik and Ustimenko 
constructed the family of graphs 
$D(n,q)$, $n\ge 2$, $q$ a prime power, 
for which $\gamma \ge \log _q(q-1)$. 
Graphs $D(n,q)$ are $q$-regular of order $2q^n$ and girth
at least $n+4$ (respectively, $n+5$) for $n$ even
(respectively, $n$ odd).
These are defined as follows.

 
Let $q$ be a prime power, and let $P$ and $L$ be two
copies of the countably infinite dimensional vector 
space over $GF(q)$.
In order to distinguish
between vectors from $P$ and $L$ we use parentheses and brackets:
$x\in P$ will be written as $(x)$,  and $y\in L$ as $[y]$.
Adopting  the notation
for coordinates of points and lines introduced in [10], namely, 
$$(p)=(p_1,p_{11},p_{12},p_{21},p_{22},p'_{22},p_{23},\ldots,
p_{ii},p'_{ii},p_{i,i+1},p_{i+1,i},\ldots),$$
$$[l]=[l_1,l_{11},l_{12},l_{21},l_{22},l'_{22},l_{23},\ldots,
l_{ii},l'_{ii},l_{i,i+1},l_{i+1,i},\ldots],$$
we  define an infinite  bipartite graph $D(q)$ with 
the vertex set  $P\cup L$ as follows.
We say $(p)$ is adjacent to $[l]$
if the following relations on their coordinates hold:
$$\eqalign{&l_{11}-p_{11}=l_1p_1\cr
	   &l_{12}-p_{12}=l_{11}p_1\cr
	   &l_{21}-p_{21}=l_1p_{11}\cr
	   &l_{ii}-p_{ii}=l_1p_{i-1,i}\cr
	   &l'_{ii}-p'_{ii}=l_{i,i-1}p_1\cr
	   &l_{i,i+1}-p_{i,i+1}=l_{ii}p_1\cr
	   &l_{i+1,i}-p_{i+1,i}=l_1p'_{ii}\cr}\eqno (6)$$
\smallskip
\noindent (The last four relations are defined for all $i\ge 2$.)
For each positive integer $n\ge 2$
 we obtain a finite bipartite graph $D(n,q)$ as follows. 
First, $P_n$ and $L_n$ are obtained
from $P$ and $L$, respectively,
by simply projecting each vector onto its
$n$ initial coordinates. Let the set of vertices 
of $D(n,q)$ be $P_n \cup L_n$. 
Adjacency in $D(n,q)$ is now defined in terms of 
the first $n\!-\!1$ relations of 
(6), and no others. 
(Note that these relations involve only
the first $n$ coordinates of vectors from
$P\cup L$, so apply unambiguously to vectors 
from $P_n \cup L_n$.)

 
In [12], Lazebnik, Ustimenko and Woldar showed that 
the graphs $D(n,q)$ are disconnected for $n\ge 6$ and 
that their connected components 
$C\!D(n,q)$ (all isomorphic) 
have order at most 
$2q^{n-\lfloor {{n+2}\over 4}\rfloor + 1} $. 
As $C\!D(n,q)$ and $D(n,q)$  
have the same girth, it follows
that the graphs $C\!D(n,q)$ form a family for which
$\gamma \ge {4\over 3}\log _q(q-1)$.  With few 
exceptions, these graphs provide the best known asymptotic 
lower bound for the greatest number of edges in graphs of
their order and girth. Later, in [13],  the authors proved that 
for $q$ odd, the order of $C\!D(n,q)$ is exactly
$2q^{n-\lfloor {{n+2}\over 4}\rfloor +1} $.
Combining this with a result  from  [9] 
on the existence of a girth cycle of length $n+5$ 
in $D(n,q)$ for all odd $n$ and infinitely many 
$q$, we get that the corresponding subfamily of 
graphs $C\!D(n,q)$ satisfies $\gamma = {4\over 3}\log _q(q-1)$.  

 
An important property of graphs $D(n,q)$ and $C\!D(n,q)$  is 
that they contain 
a special type of induced subgraph. These were introduced by the
 authors in [11] and 
can be described as follows. 
Let $R, S \subseteq GF(q)$, where $|R|=r\ge 1$ and  
$|S|=s\ge 1$, and let 
$$\eqalign{&P_R=\{(p)\in P_n|p_1\in R\} \cr
		&L_S=\{[l]\in L_n|l_1\in S\}.\cr}$$
\noindent
We define $D(n,q,R,S)$ to be the subgraph of $D(n,q)$ induced on
$P_R \cup L_S$. For fixed $(p)\in P_R$ and arbitrary $x\in S$, 
there exists
a unique neighbor $[l]$ of $(p)$ in $D(n,q,R,S)$
with first coordinate $l_1$ equal to $x$.  
Since there are precisely $s$ choices for $x$, the 
adjacency relations (6) 
imply that the degree
of $(p)$ in $D(n,q,R,S)$ is $s$.  Similarly, 
for any $[l]\in L_S$ the degree of $[l]$ in $D(n,q,R,S)$ is $r$. 
Therefore $D(n,q,R,S)$ is an 
%bipartite 
induced subgraph of $D(n,q)$ with bi-degree 
$s,r$ (every vertex from $P_R$ has degree $s$ and
every vertex from $L_S$ has degree $r$). 
Analogously, we denote by $C\!D(n,q,R,S)$
the induced subgraph of $C\!D(n,q)$
obtained by performing  
this procedure 
on $C\!D(n,q)$.
As with $D(n,q,R,S)$, the graph $C\!D(n,q,R,S)$ has
bi-degree $s,r$.
	   
 
\noindent{\bf F3.}  
In [9] 
F\" uredi and Seress, together with
the authors, showed that
for all $r,s, t\ge 2$,
there exists a bipartite graph of girth $2t$ and bi-degree $r,s$. 
They also showed that for all $r,s \ge t\ge 3$, there exists a 
bipartite graph with bi-degree $r,s$ and girth $2t$  of order
 $(r+s)q^{2t - 6}$, where 
$q\ge r,s$  is the smallest prime power of the form $1+mt$ for 
some integer $m\ge 1$.  This graph was constructed as 
$D(2t-5,q, R,S)$
where $R$ and $S$ were chosen in a special way.
As follows from [13], 
$C\!D(2t-5,q,R,S)$
is an $(r, 2t)$-graph of order
$2rq^{2t -5 -\lfloor {{2t-3}\over 4} \rfloor}$
when $r=s\ge t\ge 3$.

Each of the three families described in
F1-F3 can be used to improve the upper
bound in (1) for $(k,g)\in A\times B$, where both $A$
and $B$ are infinite subsets of positive integers.  
The authors expended considerable energy 
attempting to extend these improvements to a set 
$A\times B$ where $A$ and $B$ are not just 
infinite subsets of positive 
integers but have finite complements, e.g.~$
A=\{a: a\ge a_0\}$ and $B=\{b: b\ge b_0\}$,
for some positive integers $a_0,b_0$. 
We tried to do this constructively by 
considering special subgraphs of $X^{p,q}$ and $C\!D(n,q)$.

A natural way to find a $k$-regular subgraph in 
the Cayley graph $X_{p,q}$ is to restrict the
set of $p+1$ generators to a symmetric $k$-element
subset. The difficulty is to do this 
in such a way that the girth of the subgraph
equals a prescribed even integer $g$. 
Formulae (5) are not of much help here. Another
drawback to this approach is that the subgraph 
is not necessarily induced, which decreases its 
chances of having a small number of vertices 
in comparison to its valency and girth.


The situation is better 
with graphs $C\!D(n,q)$. Indeed, the subgraphs\hfil\break
$C\!D(n, q,R, R)$, $|R|=k \le q$, are not only 
$k$-regular but induced.   
Though we seem to have some additional
control on measuring the girth of these subgraphs,
an exact determination is very difficult.
Even in those cases where we know 
$g(C\!D(n,q))$ 
(equivalently, $g(D(n,q))$) explicitly,
we have not yet found a way to either
preserve this girth, or trace its change, when passing 
to induced subgraphs with given but
arbitrary valency $k$. 
All that we know with certainty is the obvious fact
that these subgraphs have girth at least 
$n+5$ for $n$ odd and $n+4$ for $n$ even,
as the same property holds for the graphs
$C\!D(n,q)$.


Our prospects of solving this problem looked rather
grim until a few months ago when  new results 
came in a rather unexpected way.  First, we 
discovered a simple 
way to construct families of
$(k,g)$-graphs from those 
of $k$-regular graphs of girth at least $g$. 
Applying this construction to the graphs 
$C\!D(2\lfloor{{g+1}\over{2}}\rfloor -5,q)$, 
we obtained the upper bounds given in (3) and (4). 
Soon after, we realized that we had overlooked a
beautiful result of Erd\H os and Sachs, which
asserts that the orders of $k$-regular graphs of girth 
{\it at least} $g$ provide upper bounds on the orders of
$(k,g)$-cages. Namely,

\noindent{\bf Theorem 2.1 [7]} {\it   Let $G$
 be a $k$-regular graph of girth at least $g$ 
having the least number of vertices. Then  the
 girth of $G$ is $g$ and the diameter of $G$ is at 
most $g$.}

A proof of this theorem can be found in 
[14, pp.~66, 384, 385], see also the references 
therein. Applying it to the $k$-regular subgraphs 
$C\!D(n, q,R,R)$ of $C\!D(n,q)$,
where $n=2\lfloor{{g+1}\over{2}}\rfloor -5$ and 
$|R| = k \le q$, one immediately obtains
the general nonconstructive upper bounds given 
in (2) which are better than those given in (1).
The modulo 4 classification is trivial; 
thus Theorem A is proven.

\bigskip
\noindent{\bf 3. Constructions}
\medskip
As we mentioned in the Introduction,  
for $k\ge t\ge 3$ and $q$ the smallest prime power
for which $q\ge k$ and $q\equiv 1\;{\rm mod\;}  t$,  
$(k, 2t)$-graphs whose orders are at least as 
large as  the upper bound in (2) were constructed
 by F\" uredi, Seress and the authors, see [9].
 The fact that the orders of these constructions
 actually meet the upper bound in (2) for $q$ odd 
follows from [13]. Therefore the constructions 
we present below are interesting mainly for $k < g/2$.
Before proceeding, we mention that in every case
the graphs we construct
can be viewed, roughly, as being formed by
appending an appropriate number of 
high girth graphs to a ``central'' $g$-cycle.

\medskip
\noindent{\bf Case 1: $g$ even.} Let  $k\ge 3$ 
be an integer, $g = 2s\ge 4$ an even integer, and 
$C = v_1v_2\ldots v_{2s}v_1$ a cycle of order $g$.
Let $\{H_{ij}\}$ be an arbitrary family of
$k$-regular graphs, each of order $v$ and girth at least $g$,
$1\le i\le s$, $1\le j \le k-2$. 
In each $H_{ij}$ choose, arbitrarily, a
``distinguished'' edge and  denote it by
$a_{ij}b_{ij}$.
Now, denote by  $H^*_{ij}$ the graph obtained
from $H_{ij}$ by deleting edge
$a_{ij}b_{ij}$.
Finally, form the graph $H$ by adjoining the
graphs $H^*_{ij}$ to the cycle $C$ in the following manner:
For each $1\le i\le s$, 
$1\le j\le k-2$, adjoin vertex 
$a_{ij}$ (respectively, $b_{ij}$)
of graph $H^*_{ij}$ to vertex $v_{2i-1}$
(respectively, $v_{2i}$) of $C$. 
It is trivial to see that $H$ is a $k$-regular
graph of order $g + s(k-2)v$ and that the
girth of $H$ is at most $g$.

Let us show that $g(H) = g$.  Let $K$ be a cycle in $H$ 
of order less than $g$. Then $K$ must contain at least 
one pair of edges of the form 
$a_{i_0j_0}v_{2i_0-1}$, 
$b_{i_0j_0}v_{2i_0}$, as otherwise $K$ 
would be a cycle in either $C$ or $H_{ij}$  
for some $i,j$.
But now the portion of 
$K$ which lies in $H^*_{i_0j_0}$, together
with the edge 
$a_{i_0j_0}b_{i_0j_0}$, forms a cycle in 
$H_{i_0j_0}$ of order less than $g$.

Now, taking each $H_{ij}$ to be the
$k$-regular subgraph 
$C\!D(g-5, q,R,R)$ of  $C\!D(g-5,q)$,
where $q$ is the smallest odd prime power
for which $q\ge k=|R|$,
we obtain 
the order of $H$ as appears in (3).
\medskip


\noindent{\bf Case 2: $g$ odd.}  
Let $k\ge 3$ be an integer, $g = 2s-1\ge 3$ 
an odd integer, and  
$C = v_1v_2\ldots v_{2s-1}v_1$ a cycle of order $g$.
Adjoin a new vertex $v_{2s}$ to 
$v_{2s-1}$ but to no other vertex of $C$.

With $\{H_{ij}\}$,
$a_{ij}b_{ij}$,
and $H^*_{ij}$ ($1\le i\le s$, $1\le j \le k-2$)
defined exactly as in Case 1,
we form $H$ as follows:
For each $1\le i\le s-1$, 
$1\le j\le k-2$, adjoin vertex 
$a_{ij}$ (respectively, $b_{ij}$)
of graph $H^*_{ij}$ to vertex $v_{2i-1}$
(respectively, $v_{2i}$) of $C$. 
Next for each $1 \le j \le k-3$,
adjoin vertex $a_{sj}$ (respectively, $b_{sj}$)
of graph $H^*_{sj}$ to vertex $v_{2s-1}$
of $C$ 
(respectively, vertex $v_{2s}$).
Finally, adjoin {\it both} vertices
$a_{s,k-2}$ and $b_{s,k-2}$ of
$H^*_{s,k-2}$ to vertex $v_{2s}$.

It is routine to check that $H$ is $k$-regular
of order $g+1 + s(k-2)v$, and that the
girth of $H$ is at most $g$.
One uses an argument similar to that given in
Case 1 to establish that $g(H) = g$.
Taking each $H_{ij}$ to be the
$k$-regular subgraph 
$C\!D(g-4, q,R,R)$ of  $C\!D(g-4,q)$,
where $q$ is the smallest odd prime power
for which $q\ge k=|R|$,
we obtain 
the order of $H$ as appears in (4).


\bigskip
\noindent{\bf Remark.}  It is easy to see 
that the diameter of a $k$-regular 
graph of order $v$ is at least $\log _{k-1}v$
 and  that the random $k$-regular graph has  
diameter close to this lower bound,
see [5, Ch.~X3]. Though 
several explicit constructions of families 
of $k$-regular graphs with diameters close 
to $\log _{k-1}v$ are known [5, Ch.~X1] 
these all have small girth. The problem 
of constructing infinite families of graphs of 
large girth and small diameter (i.e.~with
  diameter at most $c \log _{k-1}v$, $c\ge 1$  
a constant) is far from trivial. For the Ramanujan 
graphs described in F1, diameter is 
known to be at most $2\log _{k-1}v +2$, and the 
proof of this fact is not simple. 
The upper bound on the girth
of graphs  $C\!D(n,q)$, together with
the statement in Theorem 2.1 regarding 
diameter of cages,
implies that for every
 $k\ge 3$  there exists a family of graphs of 
large girth $\{G_i\}_{i\ge 1}$ such that 
$g(G_i) \ge {4\over 3}\log _{k-1} v_i$ 
and ${\rm diam}(G_i)\le 
{4\over 3}\log _{k-1} v_i$.  We conjecture that
 the diameter of graphs $C\!D(n,q)$ is 
within an  additive constant of this 
bound. More precisely,
\medskip
\noindent{\bf Conjecture.} {\it There 
exists a positive constant $C$ such that for all 
integers $n\ge 2$ and all prime powers $q$, 
$$diam\; (C\!D(n,q)) \le (\log _{q-1} q) n + C.$$}
\vfil\eject
\centerline{\bf References}
\bigskip
\begingroup
\baselineskip=10pt
 
\item{1.}  N. Alon, Tools from Higher Algebra, in: Handbook of 
Combinatorics, Volume II (edit. R.~L.~Graham, M.~Gr\"otschel, 
L.~Lov\'asz), MIT Press, North-Holland, New York, 1995.

\item{2.}  N.~L.~Biggs, Algebraic Graph Theory (2nd ed.), 
Cambridge University Press, 
1993.

\item{3.}  N.~L.~Biggs and A.~G.~Boshier, 
Note on the girth of Ramanujan graphs,
 {\sl Journal of Combinatorial Theory} Series 
{ B}, vol. 49 , 190-194 (1990).

\item{4.} B.~Bollob\'as, Extremal Graph 
Theory, Academic Press, London,
1978.

\item{5.} B.~Bollob\'as,  Random Graphs,
 Academic Press, London,
1985.  

\item{6.} A.~E.~Brouwer, A.~M.~Cohen, A.~Neumaier, 
 Distance-Regular Graphs,
Springer-Verlag, Heidelberg -- New York, 1989.     

\item{7.} P.~Erd\H os and H.~Sachs, Regul\"are Graphen 
gegebener
Taillenweite mit minimaler Knotenzahl,
 {\sl Wiss.~Z.~Univ.~Halle
Martin Luther Univ.~Halle--Wittenberg Math.--Natur.Reine} {12} 
(1963), 251-257.

\item{8.}  D.~A.~Holton, J.~Sheehan, 
The Petersen Graph, Australian Mathematical Society, Lecture 
Notes 7, Cambridge University Press, 1993.

\item{9.}  Z.~F\" uredi, F.~Lazebnik, \'A.~Seress, 
V.~A.~Ustimenko, A.~J.~Woldar, 
Graphs of prescribed girth and bi-degree, {\sl Journal of 
Combinatorial Theory} Ser. { B} 64 (2) (1995), 228-239.

\item{10.} F.~Lazebnik, V.~A.~Ustimenko,
 Explicit construction of graphs with
arbitrary large girth and of large size, 
 {\sl Discrete Applied Mathematics} 60 (1995), 275-284.

\item{11.} F.~Lazebnik, V.~A.~Ustimenko, A.~J.~Woldar, 
New constructions of bipartite graphs on $m,n$ vertices, with
many edges, and without small cycles,
{\sl Journal of Combinatorial Theory}
Ser. {B} 61 (1)  (1994), 111-117.

\item{12.} F.~Lazebnik, V.~A.~Ustimenko, A.~J.~Woldar, 
A new series of dense graphs of high girth, 
{\sl Bulletin of the AMS} 32 (1) (1995), 73-79.

\item{13.}
  F.~Lazebnik, V.~A.~Ustimenko, A.~J.~Woldar,
A characterization of the components of the graphs $D(k,q)$,
 {\sl Discrete Mathematics} 157 (1996) 271--283.

\item{14.} L.~Lov\'asz, Combinatorial Problems and Exercises, 
North-Holland,
Amsterdam, 1979. 

\item{15.} A.~Lubotzky, R.~Phillips, R.~Sarnak, 
Ramanujan graphs, {\sl Combinatorica} {8 (3)} (1988), 261-277.

\item{16.} G.~A.~Margulis, Explicit group-theoretical construction 
of combinatorial\hfil\break
schemes and their application to the design of 
expanders and concentrators,
{\sl Journal of Problems of Information Transmission} (1988), 39-46.

\item{17.} H.~L.~Montgomery, Topics in Multiplicative Number Theory,
{\sl Lecture Notes in Mathematics} 227, Springer Verlag, New York, 1971.

\item{18.}  G.~Royle, Cubic cages, 
http://www.ss.uwa.edu.au/gordon/cages/index.html.

\item{19.} H.~Sachs, Regular graphs with 
given girth and restricted
circuits, {\sl J. London Math. Society} 
{38} (1963), 423-429.

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

\item{21.}  H.~Walther, Eigenschaften von 
regul\" aren Graphen gegebener Taillenweite 
und minimaler Knotenzahl, 
{\sl Wiss.~Z.~Ilmenau} 11 (1965), 167-168.

\item{22.}  H.~Walther, \" Uber regul\" are Graphen 
gegebener Taillenweite 
und minimaler Knotenzahl, {\sl Wiss.~Z.~Techn.~Hochsch.~Ilmenau} 
{11}  (1965), 93-96.

\item{23.}  P.-K.~Wong, Cages -- A Survey, 
{\sl Journal of Graph Theory}
Vol.~6 (1982), 1-22.


\endgroup

\bye



.
