# Inequality regarding diameter, maximum order and number of vertices.

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

-
You might wish to look into Moore graphs. –  Joseph Zambrano Apr 7 at 19:24

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).

-

I'd say the minimum value of the diameter is 2, since no matter how many vertices you have, the graph can just be a star which has diameter 2.

-
how does that take into account the maximum degree $x$? –  Jorge Fernández Apr 10 at 3:25
If the maximum degree is then the graph must be a cycle making the maximum degree $\lfloor\frac{n}{2}\rfloor$ –  Jorge Fernández Apr 10 at 3:27
I might be wrong here, but I don't see any relation between the maximum degree and the diameter of a graph. Take a star as an example, with vertex v as the center vertex. You can add as many leaves to the graph as you want to and make them only adjacent to v. By doing that, the you can make the degree of v as big as you want to, hence you can make the maximum degree as big as you want to, without increasing the diameter which is still 2 –  Nasenhaar Apr 10 at 14:37

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)$.

-