Solution of the Chen-Chvátal conjecture for specific classes of metric spaces

Abstract

In a metric space $ (X, d) $, a line induced by two distinct points $ x, x'\in X $, denoted by $ \mathcal{L}\{x, x'\} $, is the set of points given by $ \mathcal{L}\{x, x'\} = \{z\in X:\, d(x, x') = d(x, z)+d(z, x') \text{ or }d(x, x') = |d(x, z)-d(z, x')|\}. $ A line $ \mathcal{L}\{x, x'\} $ is universal whenever $ \mathcal{L}\{x, x'\} = X $. Chen and Chvátal [Discrete Appl. Math. 156 (2008), 2101-2108.] conjectured that every finite metric space on $ n\ge 2 $ points either has at least $ n $ distinct lines or has a universal line. In this paper, we prove this conjecture for some classes of metric spaces. In particular, we discuss the classes of Cartesian metric spaces, lexicographic metric spaces and corona metric spaces.

Keywords

• de bruijn-erdős theorem
• chen-chvátal conjecture
• metric space
• lexicographic metric space
• corona metric space