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?


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.

| cite | improve this answer | |
  • $\begingroup$ Indeed, in Bollobas' Random Graphs (1985), for fixed $r\geq3$: Ch. VII. Connectivity and Matchings, Theorem 32 implies that almost every $r$-regular graph is $r$-connected; Ch. X. The Diameter, Theorem 14 implies that almost every $r$-regular graph has diameter $O_r(\log n)$. $\endgroup$ – D. Ror. Mar 11 '17 at 3:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.