Abstract
A well-known combinatorial theorem says that a set of n non-collinear points in the plane determines at least n distinct lines. Chen and Chvátal conjectured that this theorem extends to metric spaces, with an appropriated definition of line. In this work, we prove a slightly stronger version of Chen and Chvátal conjecture for a family of graphs containing chordal graphs and distance-hereditary graphs.
Original language | English |
---|---|
Pages (from-to) | 77-88 |
Number of pages | 12 |
Journal | Journal of Graph Theory |
Volume | 87 |
Issue number | 1 |
DOIs | |
Publication status | Published - Jan 2018 |
Keywords
- Chen-Chvatal conjecture
- graphe metric
ASJC Scopus subject areas
- Geometry and Topology