A graph with central points colored red

The center of a graph is the set of all vertices of minimum eccentricity. Equivalently, it is the set of vertices with eccentricity equal to the graph's radius. Thus vertices in the center (central points) minimize the maximal distance from other points in the graph.

Finding the center of a graph is useful in facility location problems where the goal is to minimize the worst-case distance to the facility. For example, placing a hospital at a central point reduces the longest distance the ambulance has to travel.

References

• James A. McHugh, Algorithmic Graph Theory (Post-Script and PDF)