2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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

$\endgroup$

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.