THE W-MEDIAN OF A CONNECTED STRONGLY CHORDAL GRAPH

Abstract

Suppose G = (V,E) is a graph in which every vertex x has a non-negative real number w(x) as its weight. The w-distance sum of a vertex y is D(G,W)(y) = SIGMA(xis-an-element-ofV) d(y,x)w(x). The w-median of G is the set of all vertices y with minimum w-distance sum D(G,W)(y). This paper shows that the w-median of a connected strongly chordal graph G is a clique when w(x) is positive for all vertices x in G. (C) 1994 John Wiley & Sons, Inc.