For all positive integers r and d that satisfy r ≤ d ≤ 2r, construct a simple graphwith radius r and diameter d.

문제출처

광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 5

Solution

(c) Construct a simple graph with radius $r$ and diameter $d$

Construction:

1. Consider the cycle $C_{2r}$ defined on $V = {0, 1, 2, \dots, 2r-1}$.

   • In this case, we have:
     $$\text{rad}(C_{2r}) = r.$$
   • When $d = r$, the graph satisfies:
     $$\text{diam}(C_{2r}) = \text{rad}(C_{2r}) = r.$$

2. Now assume $2r \geq d > r$.

   • Define a path $P_{d-r}$ starting from a vertex $r \in V$, with a length of $d-r$, consisting of vertices $r - v_1 - v_2 - \dots - v_{d-r}$, where $v_i \notin V$.
   • Define $G = C_{2r} \cup P_{d-r}$.

Verification:

1. Starting from vertex $0$, a path of length $d$ can be created to vertex $v_{d-r}$. Therefore:
   $$\text{diam}(G) = d.$$

2. The shortest path from any vertex to $r$ must include $r$. Thus:
   $$\epsilon_G(v) = \epsilon_G(r) = r.$$

3. Therefore:
   $$\text{rad}(G) = r.$$

Thus, $G$ is a simple graph with radius $r$ and diameter $d$ satisfying $r \leq d \leq 2r$.