The Chen-Chvátal conjecture for metric spaces induced by distance-hereditary graphs

Abstract

A special case of a theorem of De Bruijn and Erdős asserts that any noncollinear set of $n$ points in the plane determines at least $n$ distinct lines. Chen and Chvátal 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$.

11 pages, 0 figures

References in corpus (1)

• Number of lines in hypergraphs

Cited by in corpus (2)

• Lines in metric spaces: universal lines counted with multiplicity
• Lines, betweenness and metric spaces