How can you construct 3-regular graphs with minimal diameter?

Question

Given an even $N$, is it possible to procedurally construct a 3-regular graph $G$ with $N$ vertices such that the maximum distance between any pair of vertexes is the minimum possible for that $N$? I know that a cube, for example, is the solution for $N = 8$, but what about other N's?

Answer 1

The interesting case is connected 3-regular graphs (otherwise the diameter is infinite). We can simply show that if $G$ is such a graph then $D(G)=\Omega\left(\log_2|V|\right)$, where $D(G)$ denotes the diameter of the graph $G$.

Suppose $D(G)=d$. Start at an arbitrary vertex $v\in V$ and begin counting the vertices of the graph by scanning $G$ using BFS originating at $v$. In the first step you encounter 3 vertices ($v$'s neighbors). If at the $i'th$ step you encountered $k$ new vertices, then at the $i+1$ step you will encounter at most $2k$ new vertices (you have three edges to choose from, but at least one will take you back to a vertex you have already met). After at most $d$ steps you will encounter all of $G$'s vertices. This yields the following inequality:

$|V|\le 1+\sum\limits_{i=1}^{d-1}3\cdot 2^{i-1}=1+3\cdot \left(2^{d-1}-1\right)$, hence $d=\Omega\left(\log_2|V|\right)$.

You can see from the above that if $G$ is a connected d-regular graph then $D(G)=\Omega\left(\log_{d-1}G\right)$.

To construct a graph which achieves this lower bound, think about binary trees, and find a way to fix the leaves (and root) in order to achieve 3-regularity.