Graph radius rad(G) = min ecc(v): minimum eccentricity. The center C(G) = {v : ecc(v)=rad(G)}. For trees, the center is always 1 or 2 adjacent vertices (Jordan 1869). rad(K_n)=1, rad(P_n)=⌈(n-1)/2⌉.
How to Use
Select graph:
- Radius: Min eccentricity
- Center: Central vertices
- Relation: rad ≤ diam ≤ 2rad
Jordan's Theorem
In every tree, the center consists of 1 or 2 adjacent vertices. Found by repeatedly removing leaves: the last remaining vertex/edge is the center. This is a beautiful O(n) algorithm.
Radius-Diameter
Always rad(G)≤diam(G)≤2·rad(G). The lower bound is trivial. The upper bound: if ecc(c)=rad, then d(u,v)≤d(u,c)+d(c,v)≤2·rad for the center c. Both bounds are tight.
Step-by-Step Instructions
- 1Select graph.
- 2Compute radius.
- 3Find center.
- 4Compare to diameter.
- 5Check bounds.