00562607

j

00562607 Berrachedi, Abdelhafid A new characterization of median graphs. Discrete Math. 128, No.1-3, 385-387 (1994). 1994 Elsevier Science B.V. (North-Holland), Amsterdam EN distances Hilbertian graphs shortest path median graph

doi:10.1016/0012-365X(94)90128-7

Given two vertices $u$ and $v$ of a graph, the interval $l(u,v)$ is the set of vertices lying on some shortest path from $u$ to $v$. A graph is a median graph, if for any three vertices $u$, $v$ and $w$, the intersection of the intervals $l(u,v)$, $l(u,w)$ and $l(v,w)$ is a one- element set. A graph is Hilbertian if for any three vertices $u$, $v$ and $w$, the interval $l(u,v)$ contains the unique nearest vertex from $w$. The author shows that a graph is median if and only if it is Hilbertian. L.\v{S}olt\'es (Memphis)