4
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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.
    Commented Mar 11, 2017 at 3:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .