Let $md\_r^k(n)$ be the minimum diameter over all $r$-regular, $k$-connected graphs on at least $n$ vertices. (Let us assume $r, k \geq 2$).



> 
> **Problem:** Find lower and upper asymptotic bounds on $md\_r^k(n)$.
> 
> 
> 


There are fewer than $r^{(d+1)}$ vertices within distance $d$ of any given vertex in an $r$-regular graph; this implies the following trivial lower bound.



> 
> **Fact:** $\log\_rn \ll\_n md\_r^k(n)$.
> 
> 
> 


Jackson & Parson [[1982](http://dx.doi.org/10.1016/0095-8956(82)90001-6)] showed that for every $\varepsilon > 0$ there exist arbitrarily large $r$-regular, $r$-connected graphs with circumference at most $\varepsilon n$. When a graph is $2$-connected, the diameter is at most half the circumference, so we have the following upper bound when $r=k$.



> 
> **Corollary:** $md\_r^r(n) = o(n)$.
> 
> 
> 


Can we improve either of these bounds?



What is the minimum diameter of $r$-regular, $k$-connected graphs?
When $r\ge 3$ it's not too hard to prove that a random $r$-regular graph on $n$ vertices has diameter on the order $\log n$ and is $r$-connected with positive probability. This is in Bollobas' Random Graphs book: there is a section on random regular graphs. If you want specified smaller connectivity, add a (fixed size) gadget to reduce the connectivity before generating the random regular graph. You probably have to re-do the analysis then (as the random model is a little different) but it shouldn't be hard.


