# Graph center
> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Graph_center
> Markdown URL: https://mediated.wiki/source/Graph_center.md
> Source: https://en.wikipedia.org/wiki/Graph_center
> Source revision: 1180377955
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)
{{Short description|Set of all vertices of minimum eccentricity}}
{{Use American English|date=March 2021}}
{{Use mdy dates|date=March 2021}}
thumb|right|A graph with central points colored red. These are the three vertices ''A'' such that ''d''(''A'', ''B'') ≤ 3 for all vertices ''B''. Each black vertex is a distance of at least 4 from some other vertex.
The '''center''' (or [Jordan](/source/Camille_Jordan) center[[Wasserman, Stanley](/source/Wasserman%2C_Stanley), and Faust, Katherine (1994), ''Social Network Analysis: Methods and Applications'', page 185. Cambridge: Cambridge University Press. {{ISBN|0-521-38269-6}}]) of a [graph](/source/Graph_(discrete_mathematics)) is the set of all vertices of minimum [eccentricity](/source/Eccentricity_(graph_theory)),[McHugh, James A., [http://www.cs.njit.edu/mchugh/psswrd/web-course-materials/graph-theory/alg-graph-theory-text-html/chap-1-text-v3.html Algorithmic Graph Theory] {{Webarchive|url=https://web.archive.org/web/20100801092700/http://www.cs.njit.edu/mchugh/psswrd/web-course-materials/graph-theory/alg-graph-theory-text-html/chap-1-text-v3.html |date=2010-08-01 }}] that is, the set of all vertices ''u'' where the greatest distance ''d''(''u'',''v'') to other vertices ''v'' is minimal. Equivalently, it is the set of vertices with eccentricity equal to the graph's [radius](/source/radius_(graph_theory)).[{{MathWorld | urlname=GraphCenter| title = Graph center}}] Thus vertices in the center ('''central points''') minimize the maximal distance from other points in the graph.
This is also known as the '''vertex 1-center problem''' and can be extended to the [vertex k-center problem](/source/vertex_k-center_problem).
Finding the center of a graph is useful in [facility location problem](/source/Optimal_facility_location)s 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 center can be found using the [Floyd–Warshall algorithm](/source/Floyd%E2%80%93Warshall_algorithm).[Floyd, Robert W. (June 1962). "Algorithm 97: Shortest Path". Communications of the ACM. 5 (6): 345 https://doi.org/10.1145/367766.368168][Warshall, Stephen (January 1962). "A theorem on Boolean matrices". Journal of the ACM. 9 (1): 11–12 https://doi.org/10.1145/321105.321107] Another algorithm has been proposed based on matrix calculus.[{{Cite web|url=https://hal.archives-ouvertes.fr/hal-02304090|title=A new algorithm for graph center computation and graph partitioning according to the distance to the center|date=October 2019}}]
The concept of the center of a graph is related to the [closeness centrality](/source/closeness_centrality) measure in [social network analysis](/source/social_network_analysis), which is the reciprocal of the mean of the distances ''d''(''A'',''B'').