  We derive attainable upper bounds on the algebraic connectivity (spectral
gap) of a regular graph in terms of its diameter and girth. This bound agrees
with the well-known Alon-Boppana-Friedman bound for graphs of even diameter,
but is an improvement for graphs of odd diameter. For the girth bound, we show
that only Moore graphs can attain it, and these only exist for very few
possible girths. For diameter bound, we use a combination of stochastic
algorithms and exhaustive search to find graphs which attain it. For 3-regular
graphs, we find attainable graphs for all diameters $D$ up to and including
$D=9$ (the case of $D=10$ is open). These graphs are extremely rare and also
have high girth; for example we found exactly 45 distinct cubic graphs on 44
vertices attaining the upper bound when $D=7$; all have girth 8 (out of a total
of about $10^{20}$ cubic graphs on 44 vertices, including 266362 having girth
8). We also exhibit families of $d$-regular graphs attaining upper bounds with
$D=3$ and $4$, and with $g=6.$ Several conjectures are proposed.
