THE MEDIAN PROCEDURE ON MEDIAN GRAPHS

A median of a profile pi = (x(l),..., x(k)) of vertices of a finite co nnected graph G is a vertex x for which Sigma(i=1)(k), d(x,x(i)) is mi nimum, where d is the usual geodesic distance on G. The function Med w hose domain is the set of all profiles and is given by Med(pi) = {x : x is a median of pi} is called the median procedure on G. In this pape r, the median procedure is characterized for median graphs and cube-fr ee median graphs. (C) 1998 Elsevier Science B.V. All rights reserved.