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?

  • $\begingroup$ Having $\frac{3}{2}|V|$ edges is not equivalent to being 3-regular, are you focusing only on 3-regular graphs? $\endgroup$
    – Ariel
    Dec 31 '16 at 16:49
  • $\begingroup$ Yes, I guess that is the name. $\endgroup$
    – MaiaVictor
    Dec 31 '16 at 17:50

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.


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.