 Center of a graph

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.