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.

Given a $k$-regular graph, its diameter is bounded by $O(n/k)$ where $n$ is the number of nodes and $k$ is the degree of each node.

Is there any straight-forward way to prove this result?

share|improve this question
    
Is this true? Is it bounded by n/k or O(n/k)? –  Vinicius dos Santos Apr 5 '13 at 8:36
1  
It is actually not bounded by n/k. Take for example the following 3-regular graph: start with one vertex adjacent to all the vertices of a path on 3 vertices. Join the two extremity to an other vertex, says u. do a copy of this graph with v the copy of u and join u and v. This graph has diameter 5, 10 vertices and degree 3. This example can easily be generalized. The correct bound seems to be something like $3n/k$ (see discuss.fogcreek.com/joelonsoftware3/…) –  Aline Parreau Apr 5 '13 at 8:42
    
Sorry, it should be O(n/k) –  Jeremy Apr 5 '13 at 8:52
1  
If $k$ is fixed as $n \rightarrow \infty$, then $n=O(n)=O(n/k)$. I suspect this is not what you want either. –  Douglas S. Stones Apr 5 '13 at 12:56
add comment

1 Answer

up vote 5 down vote accepted

I won't give a complete answer, but a hint that should be enough.

Let $d$ be the diameter of a graph $G$ and let $u, v$ be vertices satisfying $dist(u,v) = d$. Now let $S_i$ be the set of vertices $w$ such that $dist(u,w) = i$. Finally, consider a shortest path $P$ between $u$ and $v$.

Remember that $G$ is $k$-regular. Note that the neighbors of the vertex in $S_i \cap P$ need to be in $S_{i-1}$, $S_i$ and $S_{i+1}$ (otherwise you would have a contradiction with the minimality of $P$) and hence $|S_{i-1}| +|S_{i}| + |S_{i+1}| \geq k$. What are the consequences of $|S_{i-1}| + |S_{i}| +|S_{i+1}| \geq k$?

share|improve this answer
    
I understand your idea. But I guess it is also possible for a vertex in $S_i$ to have a neighbour also in $S_i$. So $|S_{i-1}| + |S_i| + |S_{i+1}| \geq k$. –  Jeremy Apr 5 '13 at 9:31
    
Sure! Stupid me. I will fix it. –  Vinicius dos Santos Apr 5 '13 at 13:21
add comment

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.