A new class of graphs that satisfies the Chen-Chvátal conjecture

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 Chvatal 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 Chvatal conjecture for a family of graphs containing chordal graphs and distance-hereditary graphs.