pith. sign in

arxiv: 1312.3214 · v2 · pith:3SPRQD2Qnew · submitted 2013-12-09 · 🧮 math.MG · cs.DM· math.CO

The Chen-Chv\'atal conjecture for metric spaces induced by distance-hereditary graphs

classification 🧮 math.MG cs.DMmath.CO
keywords metricdistance-hereditaryinducedspacesatalconnecteddistancegraphs
0
0 comments X
read the original abstract

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$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.