MEDIAN GRAPHS AND HELLY HYPERGRAPHS

One-to-one correspondences are established between the following combinatorial structures: (i) median interval structures (or median segments, introduced by Sholander); (ii) maximaL Helly hypergraphs such that with each edge also its complement is in the hypergraph; and (iii) median graphs (connected graphs such that for any three vertices u, v, w there is exactly one vertex x such that d(u,υ) = d(u,x)+d(x,υ), d(υ,w) = d(υ,x)+d(x,w) and d(w, u) = d(w,x)+ d(x, u), where d is the distance function of the graph). © 1979.