From Distances to the Center
A complete distance table collects the shortest-path distance between every pair of vertices. Once the table is available, the key calculation is simple: the largest entry in a vertex’s row is its eccentricity. Comparing these row maxima gives the radius, diameter, center, and peripheral vertices. The care lies in reading the extrema correctly and making sure the table entries really are shortest-path distances.
Throughout, graphs are finite, simple, undirected, connected, and nonempty. The distance \(d(u,v)\) is the length of a shortest path from \(u\) to \(v\). In a connected graph every such distance is finite, and \(d(v,v)=0\).
In a distance table, rows and columns are indexed by the graph’s vertices, and the entry in row \(v\), column \(u\) is \(d(v,u)\). The table is symmetric because \(d(v,u)=d(u,v)\), and its diagonal entries are zero. The row maximum—not the row sum or average—is the eccentricity. A complete table is useful because it lets us compare every vertex using the same data.
Why Row Maxima Give the Needed Quantities
Proof. Fix a vertex \(v\). The entries in its row are exactly the distances \(d(v,u)\) as \(u\) ranges over all vertices of the graph. By definition, \(\operatorname{ecc}(v)\) is the greatest of those distances, so it equals that row’s maximum. Taking the minimum of the row maxima over all vertices gives the radius by its definition, and taking their maximum gives the diameter. The vertices attaining the minimum are exactly those with eccentricity equal to the radius, which is the center; the vertices attaining the maximum are exactly those with eccentricity equal to the diameter, which are the peripheral vertices. \(\square\)
These extrema exist: the graph has a finite, nonempty vertex set, so the finite, nonempty list of row maxima has both a least and a greatest value. Thus every graph under the standing assumptions has at least one central vertex and at least one peripheral vertex. A vertex may belong to both sets.
For each vertex, collect the entries in its row. The diagonal entry is zero, and the other entries are distances to the remaining vertices.
Record one eccentricity for every vertex. Do not average the distances.
The least is the radius and the greatest is the diameter. Record every vertex attaining each value.
Vertices listed as central must attain the least row maximum; vertices listed as peripheral must attain the greatest.
Worked Distance Tables
Worked Example: A Path with One Central Vertex
Let \(G\) have \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,23,34,45\}\). This is the path \(P_5\). There is a unique path between any two vertices, so the distance from \(i\) to \(j\) is \(|i-j|\). Applying that formula to each pair gives the complete table:
| \(d(u,v)\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) |
|---|---|---|---|---|---|
| \(1\) | 0 | 1 | 2 | 3 | 4 |
| \(2\) | 1 | 0 | 1 | 2 | 3 |
| \(3\) | 2 | 1 | 0 | 1 | 2 |
| \(4\) | 3 | 2 | 1 | 0 | 1 |
| \(5\) | 4 | 3 | 2 | 1 | 0 |
The row maxima, computed from the displayed entries, are \(\operatorname{ecc}(1)=\max\{0,1,2,3,4\}=4\), \(\operatorname{ecc}(2)=\max\{1,0,1,2,3\}=3\), \(\operatorname{ecc}(3)=\max\{2,1,0,1,2\}=2\), \(\operatorname{ecc}(4)=\max\{3,2,1,0,1\}=3\), and \(\operatorname{ecc}(5)=\max\{4,3,2,1,0\}=4\). The least eccentricity is \(2\), so \(\operatorname{rad}(G)=2\) and the center is \(\{3\}\). The greatest eccentricity is \(4\), so \(\operatorname{diam}(G)=4\) and the peripheral vertices are \(\{1,5\}\).
Check: Vertex \(3\) is two edges from each endpoint, so its greatest distance is \(2\). Vertex \(1\) is four edges from vertex \(5\), and vertex \(5\) is four edges from vertex \(1\). These facts verify the central and peripheral values read from the table.
Worked Example: Every Vertex Is Central and Peripheral
Let \(G\) have \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,23,34,45,51\}\), the cycle \(C_5\). From any vertex, the two adjacent vertices are at distance \(1\), and the other two vertices are each at distance \(2\), by taking the shorter direction around the cycle. Thus the complete table is:
| \(d(u,v)\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) |
|---|---|---|---|---|---|
| \(1\) | 0 | 1 | 2 | 2 | 1 |
| \(2\) | 1 | 0 | 1 | 2 | 2 |
| \(3\) | 2 | 1 | 0 | 1 | 2 |
| \(4\) | 2 | 2 | 1 | 0 | 1 |
| \(5\) | 1 | 2 | 2 | 1 | 0 |
Each row has maximum \(2\): the row maxima are \(\max\{0,1,2,2,1\}=2\), \(\max\{1,0,1,2,2\}=2\), \(\max\{2,1,0,1,2\}=2\), \(\max\{2,2,1,0,1\}=2\), and \(\max\{1,2,2,1,0\}=2\). Therefore every vertex has eccentricity \(2\). It follows that \(\operatorname{rad}(G)=2\), \(\operatorname{diam}(G)=2\), the center is \(\{1,2,3,4,5\}\), and the peripheral vertices are also \(\{1,2,3,4,5\}\).
Check: From vertex \(1\), the distances to \(2\) and \(5\) are \(1\), while the routes to \(3\) and \(4\) have lengths \(2\) in the shorter direction. Rotating the cycle gives the same pattern at every vertex, in agreement with all five row maxima.
Worked Example: A Center with Two Vertices
Let \(G\) have \(V(G)=\{a,b,c,d,e\}\) and \(E(G)=\{ab,bc,ca,cd,de\}\). The vertices \(a,b,c\) form a triangle, and the path \(c,d,e\) extends from \(c\). Within the triangle, each pair is joined by an edge. The distances from \(a\) and \(b\) to \(d\) are \(2\), using \(c\), and their distances to \(e\) are \(3\), using \(c,d\). Also \(d(c,d)=1\), \(d(c,e)=2\), and \(d(d,e)=1\). These give the full table:
| \(d(u,v)\) | \(a\) | \(b\) | \(c\) | \(d\) | \(e\) |
|---|---|---|---|---|---|
| \(a\) | 0 | 1 | 1 | 2 | 3 |
| \(b\) | 1 | 0 | 1 | 2 | 3 |
| \(c\) | 1 | 1 | 0 | 1 | 2 |
| \(d\) | 2 | 2 | 1 | 0 | 1 |
| \(e\) | 3 | 3 | 2 | 1 | 0 |
Taking row maxima gives \(\operatorname{ecc}(a)=\max\{0,1,1,2,3\}=3\), \(\operatorname{ecc}(b)=\max\{1,0,1,2,3\}=3\), \(\operatorname{ecc}(c)=\max\{1,1,0,1,2\}=2\), \(\operatorname{ecc}(d)=\max\{2,2,1,0,1\}=2\), and \(\operatorname{ecc}(e)=\max\{3,3,2,1,0\}=3\). Hence the radius is \(2\), the diameter is \(3\), the center is \(\{c,d\}\), and the peripheral vertices are \(\{a,b,e\}\).
Check: The greatest distances from \(c\) and \(d\) are both \(2\). Each of \(a,b,e\) is at distance \(3\) from at least one vertex: \(a\) and \(b\) are each \(3\) from \(e\), and \(e\) is \(3\) from both \(a\) and \(b\). No table entry exceeds \(3\), so these are indeed the greatest row maxima.
Reading and Checking the Results
The center is a set of vertices, not necessarily a single vertex. The path example has one central vertex, while the final example has two. The peripheral set can also have several vertices; in the cycle example, every vertex is peripheral. When the radius and diameter are equal, every vertex is both central and peripheral: each eccentricity is at least the radius and at most the diameter, so it must equal their common value.
A distance table must record shortest-path lengths, not just lengths of paths that happen to connect the vertices. For a graph specified by its edges, check entries using actual shortest paths. An exhibited path gives an upper bound on distance; to establish that it is shortest, also rule out a shorter route. For a table supplied as complete data, the row-maximum calculation assumes its entries are already the graph distances.
Common mistake: using a row average instead of its maximum. In the \(P_5\) example, the row for vertex \(3\) is \(2,1,0,1,2\). Its average is \((2+1+0+1+2)/5=6/5\), but its eccentricity is the greatest entry, \(\max\{2,1,0,1,2\}=2\). An average describes the overall distances from the vertex; it does not give the distance to its farthest vertex. The radius and diameter must be computed from eccentricities, so replacing row maxima with averages changes the quantities being measured.
For a connected graph with just one vertex \(v\), the table consists of the single entry \(d(v,v)=0\). Its row maximum is \(0\), so its radius and diameter are both \(0\), and \(v\) is both central and peripheral. This case follows the same row-maximum rule without needing any special adjustment.
Check Your Understanding
Use row maxima throughout, and state every vertex attaining each relevant extremum.
- For \(P_5\) with vertices \(1,2,3,4,5\) in order, which vertices have eccentricity \(3\)?
- In a complete distance table, what does the greatest entry in the row of \(v\) represent?
- If every row maximum of a connected graph’s distance table is \(4\), what are its radius and diameter, and which vertices are central and peripheral?
- Explain why the average of a row is not the eccentricity, using the row for vertex \(3\) in the \(P_5\) example.
- What are the radius, diameter, center, and peripheral set for a connected graph consisting of one vertex?