Graph eccentricity ($e_G(v)={\max }_u{d}_G(v,u)$)

For a vertex $v$ of a finite connected graph $G$, its graph eccentricity is the greatest graph distance to any other vertex:The graph radius is the minimum eccentricity and the graph diameter is the maximum. Eccentricity therefore measures the worst travel distance from a chosen starting point, rather than its average travel distance.

In the four-vertex path graph $1-2-3-4$, the eccentricities are $3,2,2,3$. The two middle vertices are best in this worst-case sense; the radius is two and the diameter three. In a star graph with at least two leaves, the central vertex has eccentricity one and every leaf has eccentricity two. For a disconnected graph, distances across components are usually infinite, so a finite-valued eccentricity requires restricting to a component or stating another convention.

The graph radius of a finite connected graph $G$ is the least graph eccentricity of any vertex:It is the smallest worst-case travel distance achievable by choosing one starting vertex. The vertices achieving it form the center of a graph.

For the five-vertex path graph, the eccentricities are $4,3,2,3,4$, so the radius is two and the graph diameter is four. Every finite connected graph satisfies $\mathrm{rad}G\le \mathrm{diam}G\le 2\mathrm{rad}G$: choose a central vertex $c$ and apply the triangle inequality $d(u,v)\le d(u,c)+d(c,v)$. In a five-cycle every vertex has eccentricity two, so radius and diameter coincide. A vertex minimizing the sum of distances solves a different optimization problem.

The center of a graph is the set of vertices with minimum graph eccentricity. For a finite connected graph $G$, putHere $d_G$ is shortest-path distance and $\mathrm{rad}G={\min }_{v}e(v)$ is the graph radius. The center solves a facility-placement problem in which the cost is the distance to the farthest vertex.

In a five-vertex path graph, eccentricities are $4,3,2,3,4$, so only the middle vertex is central. In a four-vertex path, the two middle vertices both have eccentricity two. The center of a tree is always a single vertex or a pair of adjacent vertices: repeatedly deleting all leaves exposes its middle. For a general graph the center need not have this form; every vertex of a cycle graph is central.

Minimizing the sum of distances defines a different objective. For example, let $a,b,c,d$ form a path, and attach three additional leaves to $a$. The center is $\{b\}$, but the sum of distances is smallest at $a$. The farthest-distance criterion and the average-distance criterion can therefore select different locations.