Lower and upper bounds on the diameter of 3-regular graphs obtained after reducing practical real world problem instances to #3-regular Vertex Cover In the paper The diameter of random regular graphs, Bollobás and Fernandez De La Vega give asymptotic lower and upper bounds on the diameter $d$ of random $r$-regular graphs. Roughly, the lower bound is $\Theta(log_{r-1}n)$, while the upper bound is $\Theta(log_{r-1}(nlogn))$, where $n$ is the number of nodes of the graph.

I would like to know (even just empirical) lower and upper bounds on the diameter of non-random $3$-regular graphs. More precisely, such non-random $3$-regular graphs in which I'm interested are those arising after reducing practical real world problem instances (which are known to be structured instead of random) to the $\sharp P$-complete problem $\sharp3$-regular Vertex Cover. In other words, suppose you have a real-world instance of a $NP$-complete problem, and suppose you want to count its solutions: following a chain of reductions, you come out with a $3$-regular graph $G$, whose number of vertex covers encodes the number of solutions of your initial instance.


  Questions  
  
  
  How is $G$? Is it still structured, as the original instance? Or did it destroyed the initial structure?
  If $G$ is structured, which are the lower bound and the upper bound on its diameter? Do the bounds given by Bollobás and Fernandez De La Vega still hold? Or are such bounds completely different in the structured case?
  Does there exist any automated tool (along the lines of ToughSAT) that, given an instance of a $NP$-complete problem, produces the graph $G$?
A lower bound of approximately $\log_2 n$ still follows for arbitrary 3-regular graphs, based simply on the fact that there are at most $3\times 2^i$ different paths of length $i$ from any  given starting vertex and one needs the diameter to be large enough to give a different path to each of the $n$ vertices. The random graph example that you mention (or the example of a complete binary tree with some extra edges thrown in to make it 3-regular) shows that this is tight to within a constant factor, and I'm pretty sure the actual lower bound is really $(1+o(1))\log_2 n$.

As for an upper bound: there exist 3-regular graphs with diameter $\Omega(n)$, for instance the Möbius ladders.

If you want to know the diameters of graphs coming from specific hardness constructions, you'd have to look at the details of those constructions, but my guess is that in most such cases it would be straightforward to tack on either a large binary tree or a large ladder in order to make the diameter as small or as large as you want without much changing the hardness of the instance.