%0 Journal Article
%T The Chen-Chv¨˘tal conjecture for metric spaces induced by distance-hereditary graphs
%A Pierre Aboulker
%A Rohan Kapadia
%J Mathematics
%D 2013
%I arXiv
%R 10.1016/j.ejc.2014.06.009
%X A special case of a theorem of De Bruijn and Erd\H{o}s asserts that any noncollinear set of $n$ points in the plane determines at least $n$ distinct lines. Chen and Chv\'atal conjectured a generalization of this result to arbitrary finite metric spaces, with a particular definition of lines in a metric space. We prove it for metric spaces induced by connected distance-hereditary graphs -- a graph $G$ is called distance-hereditary if the distance between two vertices $u$ and $v$ in any connected induced subgraph $H$ of $G$ is equal to the distance between $u$ and $v$ in $G$.
%U http://arxiv.org/abs/1312.3214v2