The median function on median graphs and semilattices

A median of a k-tuple pi = (x(1), . . . ,x(k)) of vertices of a finite conn ected graph G is a vertex x for which Sigma(i=1)(k), d(x,xi) is minimum, wh ere d is the geodesic metric on G. The function M with domain the set of al l k-tuples with k > 0 and defined by M(pi)= {x \ x is a median of pi} is ca lled the median function on G. In this paper a new characterization of the median function is given for G a median graph. This is used to give a chara cterization of the median function on median semilattices. (C) 2000 Elsevie r Science B.V. All rights reserved.