0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Welcome to MSE. You'll get a lot more help, and fewer votes to close, if you show that you have made a real effort to solve the problem yourself. What are your thoughts? What have you tried? How far did you get? Where are you stuck? This question is likely to be closed if you don't add more context. Please respond by editing the question body. Many people browsing questions will vote to close without reading the comments. $\endgroup$ – saulspatz Sep 2 at 21:27
  • $\begingroup$ Your plan sounds great. Let's say that $r=4$ and $d=6$. You started out with a cycle of length $8$, then what specifically would you do to it to push the diameter to $6$ while keeping the radius at $4$? $\endgroup$ – Matthew Daly Sep 2 at 22:41
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.