2
$\begingroup$

Suppose I have a graph which is like this:

A--B--C--D

What is the diameter and radius of this graph?

Here r = 1 and d = 3 and r < d/2 ..right ?

  • 0
    @Brian, I guess that should be posted as an answer.2012-04-15

1 Answers 1

3

The diameter is $3$, but the radius is $2$: the eccentricities of $A,B,C$, and $D$ are $3,2,2$, and $3$, respectively, and the radius is the minimum of the eccentricities.

Note that you can never have r. If $u$ is a vertex of eccentricity $r$, and $v$ and $w$ are any vertices, there must be paths of length at most $r$ from $v$ and $w$ to $u$, so there must be a path of length at most $2r$ from $v$ to $w$. Thus, $d\le 2r$.

  • 0
    @user153695: If $G$ is not connected, the diameter and radius are both infinite, so we don’t normally talk about them.2015-03-30