A graph with central points colored red. These are the three vertices A such that d(A,B) ≤ 3. Each black vertex is a distance of at least 4 from some other vertex.

The center (or Jordan center^[1]) of a graph is the set of all vertices of minimum eccentricity,^[2] that is, the set of all vertices A where the greatest distance d(A,B) to other vertices B is minimal. Equivalently, it is the set of vertices with eccentricity equal to the graph's radius.^[3] 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.

The concept of the center of a graph is related to the closeness centrality measure in social network analysis, which is the reciprocal of the mean of the distances d(A,B).^[1]

[edit] References

1. ^ ^{a b} Wasserman, Stanley, and Faust, Katherine (1994), Social Network Analysis: Methods and Applications, page 185. Cambridge: Cambridge University Press. ISBN 0521382696
2. ^ McHugh, James A., Algorithmic Graph Theory
3. ^ Weisstein, Eric W., "Graph center" from MathWorld.

This combinatorics-related article is a stub. You can help Wikipedia by expanding it. v • d • e