4
$\begingroup$

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?

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

1 Answer 1

7
$\begingroup$

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$?

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$
    – Jeremy
    Apr 5, 2013 at 9:31
  • $\begingroup$ Sure! Stupid me. I will fix it. $\endgroup$ Apr 5, 2013 at 13:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .