Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|cite|improve this question
You might wish to look into Moore graphs. – Joseph Zambrano Apr 7 '14 at 19:24

2 Answers 2

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.