Premium
Centroids and medians of finite metric spaces
Author(s) -
Bandelt Hans JÜRgen
Publication year - 1992
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190160404
Subject(s) - mathematics , combinatorics , centroid , vertex (graph theory) , metric space , minimax , joins , metric dimension , chordal graph , metric (unit) , regular polygon , discrete mathematics , graph , geometry , 1 planar graph , mathematical optimization , computer science , operations management , economics , programming language
The median of a weighted finite metric space consists of the points minimizing the total weighted distance to the points of the space. The centroid is formed by the points p satisfying the following minimax condition: the maximal weight of a geodesically convex set not containing a point X attains its minimum at p . It is well known that in a tree network the centroid and the median coincide for every distribution of weights. The metric spaces for which the latter property is characteristic are determined in this paper. These spaces are obtained from three classess of graphs: median graphs, joins of complete graphs with edgeless graphs, and joins of two‐vertex edgeless graphs.