2025/10/22 by Martı́n Matamala, Matamala, Martín · 1 citation
Computer Science · #05C62 #05c12 #54E35 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Graph Labeling and Dimension Problems #Metric Geometry (math.MG)
paper · pdf · doi:10.48550/arxiv.2510.19601
openalex publication_date 2025/10/22 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
In 2008 Chen and Chvátal conjectured that any metric space on n points has at least n lines, unless all the points belong to one line. Chv\atal proved in 2014 that this is indeed the case for metric spaces with distances 0, 1 and 2. In this work, we prove that there exists a family of ten graphs such that a metric space defined by a graph of diameter two has fewer lines than points if and only if the associated graph belongs to that family.