Take the 2-minute tour ×
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|improve this question
2  
You might wish to look into Moore graphs. –  Joseph Zambrano Apr 7 at 19:24

3 Answers 3

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|improve this answer

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.

share|improve this answer
    
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)$.

share|improve this answer

Your Answer

 
discard

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.