What is the minimum diameter of $r$-regular, $k$-connected graphs?

Question

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] 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?

Answer 1

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.