Graph Radius — Definition, Formula & Examples

Graph radius is the smallest eccentricity among all vertices in a connected graph. It tells you the best-case "worst-case distance" — the minimum, over all vertices, of the maximum distance from that vertex to any other vertex.

For a connected graph $G = (V, E)$ , the eccentricity of a vertex $v$ is $\varepsilon(v) = \max_{u \in V} d(v, u)$ , where $d(v,u)$ is the shortest-path distance between $v$ and $u$ . The radius of $G$ is defined as $\operatorname{rad}(G) = \min_{v \in V} \varepsilon(v)$ . A vertex whose eccentricity equals the radius is called a central vertex.

Key Formula

\operatorname{rad}(G) = \min_{v \in V} \, \max_{u \in V} \, d(v, u)

Where:

$G$ = A connected graph with vertex set V and edge set E
$d(v, u)$ = Shortest-path distance between vertices v and u
$\varepsilon(v)$ = Eccentricity of vertex v, equal to max_u d(v, u)

How It Works

To find the radius, first compute the shortest-path distance between every pair of vertices. Then determine each vertex's eccentricity by taking the maximum distance from that vertex to all others. The radius is the minimum of these eccentricity values. The set of all vertices that achieve this minimum eccentricity forms the center of the graph.

Worked Example

Problem: Find the radius of the path graph on 5 vertices: v₁ — v₂ — v₃ — v₄ — v₅.

Step 1: Compute eccentricities. The farthest vertex from v₁ is v₅ at distance 4, so ε(v₁) = 4. By symmetry, ε(v₅) = 4.

\varepsilon(v_1) = \max(0,1,2,3,4) = 4

Step 2: For v₂, distances are 1, 0, 1, 2, 3, so ε(v₂) = 3. By symmetry, ε(v₄) = 3.

\varepsilon(v_2) = 3, \quad \varepsilon(v_4) = 3

Step 3: For v₃ (the middle vertex), distances are 2, 1, 0, 1, 2, so ε(v₃) = 2. Take the minimum eccentricity.

\operatorname{rad}(G) = \min(4, 3, 2, 3, 4) = 2

Answer: The radius of the path graph P₅ is 2, and v₃ is the unique central vertex.

Why It Matters

Graph radius is used in network design to find optimal locations for facilities or servers that minimize the worst-case distance to any node. It also appears in theoretical results relating radius and diameter, such as the bound

\operatorname{rad}(G) \leq \operatorname{diam}(G) \leq 2 \cdot \operatorname{rad}(G)

, which is a standard result in discrete mathematics courses.

Common Mistakes

Mistake: Confusing radius with diameter. Students sometimes take the maximum eccentricity instead of the minimum.

Correction: Radius is the minimum eccentricity (best-positioned vertex), while diameter is the maximum eccentricity (worst-positioned vertex). Remember: rad = min, diam = max.