Graph theory radius and diameter

1.3k Views Asked by At

Prove that for every two integers $r\leq s\leq 2r$ there exists $G$, a connected graph, such that $\mathrm{rad}(G)=r$ and $\textrm{diam}(G)=s$

I tried to build it: a cycle of length $2r$ (so that the radius is $R$) then I tried to add a path that would make sure it has diameter $s$, but it did not work.

2

There are 2 best solutions below

0
On

I admit to not being sure how to make your idea work OP. I mean, it may be doable that way I at the moment can't see how. This is another idea:

  1. Let $P=u_ru_{r-1}u_{r-2} \ldots u_1vv_1v_2\ldots v_r$ be a path. So $P$ has radius $r$; indeed the vertex $v$ at the midpoint of $P$ is of distance precisely $r$ from each of the two endpoints $u_r$ and $v_r$ of $P$.

  2. If $s$ is even and less then $2r$ add in the edges $u_iv_{i+1}$ and $u_{i+1}v_i$, where $i$ satisfies $2(r-i)=s$; if $s$ is odd add in the edge $u_iv_i$, where $i$ satisfies $2(r-i)+1=s$.

Note that the distance in the resulting graph between $v$ and $u_r$ and between $v$ and $v_r$ remains precisely $r$. What is the diameter of the resulting graph, for $s$ satisfying $r \le s \le 2r$?

0
On

The radius in G is the minimum eccentricity. The diameter in G is the maximum eccentricity. Let $u$ and $v$ be vertices of G such that the distance $d(u,v) = s = diam(G)$. Let $\omega$ be a central vertex so that the eccentricity $e(\omega)$ = r = rad(G). Then there exist no vertex at a distance from $\omega$ greater than r = rad(G), which means (triangle inequality): $d(w,u) + d(w,v) \leq 2.rad(G)$. Then: $r\leq s \leq 2.r$