Inequality regarding diameter, maximum order and number of vertices.

Question

Suppose I have a connected graph on $n$ vertices with maximum degree $x$. What is the minimum value of the Diameter $D$?

Answer 1

I'm coming late to this discussion, and perhaps you already know the answer, but anywyay, here it is: Let $n$ be the number of vertices of the graph, $D \geq 2$ its diameter, and $\Delta \geq 2$ the maximum degree. If $\Delta=2$, then $D \geq (n-1)/2$. For $\Delta > 2$ we have that $$D \geq \log_{\Delta-1}[(n-1)(\Delta-2)+\Delta] - \log_{\Delta-1}\Delta.$$ This comes by solving for $D$ in the Moore bound (see "Moore graphs and beyond: A survey in the Degree/Diameter Problem", by Mirka Miller and Josef Siran, Elec. J. of Combinatorics, Dynamic Survey 14).

Answer 2

If $G$ is k-regular, then the diameter is $log_{k}(n)$. So with a maximum degree, we get a lower bound as to the diameter using the same approximation: $diam(G) \geq log_{x}(n)$.