Diameter of $k$-regular graph

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?

• Is this true? Is it bounded by n/k or O(n/k)? Apr 5, 2013 at 8:36
• 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/…) Apr 5, 2013 at 8:42
• Sorry, it should be O(n/k) Apr 5, 2013 at 8:52
• If $k$ is fixed as $n \rightarrow \infty$, then $n=O(n)=O(n/k)$. I suspect this is not what you want either. Apr 5, 2013 at 12:56

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$?
• 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$. Apr 5, 2013 at 9:31