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.
Citation: Juan Alberto Rodríguez-Velázquez. Solution of the Chen-Chvátal conjecture for specific classes of metric spaces[J]. AIMS Mathematics, 2021, 6(7): 7766-7781. doi: 10.3934/math.2021452
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.
| [1] |
P. Aboulker, R. Kapadia, The Chen-Chvátal conjecture for metric spaces induced by distance-hereditary graphs, Eur. J. Combin., 43 (2015), 1–7. doi: 10.1016/j.ejc.2014.06.009
|
| [2] |
P. Aboulker, M. Matamala, P. Rochet, J. Zamora, A new class of graphs that satisfies the Chen-Chvátal conjecture, J. Graph Theory, 87 (2018), 77–88. doi: 10.1002/jgt.22142
|
| [3] | L. Beaudou, A. Bondy, X. Chen, E. Chiniforooshan, M. Chudnovsky, V. Chvátal, et al. A De Bruijn–Erdős theorem for chordal graphs, Electron. J. Comb., 22 (2015), 1–70. |
| [4] | L. Beaudou, G. Kahn, M. Rosenfeld, Bisplit graphs satisfy the Chen-Chvátal conjecture, Discrete Math. Theor. Comput. Sci., 21 (2019), 1–22. |
| [5] | N. G. de Bruijn, P. Erdős, On a combinatorial problem, Indagationes Math., 10 (1948), 421–423. |
| [6] | R. Frucht, F. Harary, On the corona of two graphs, Aequationes Math., 4 (1970), 322–325. |
| [7] |
X. Chen, V. Chvátal, Problems related to a de Bruijn-Erdős theorem, Discrete Appl. Math., 156 (2008), 2101–2108. doi: 10.1016/j.dam.2007.05.036
|
| [8] |
V. Chvátal, A de Bruijn-Erdős theorem for 1-2 metric spaces, Czechoslovak Math. J., 64 (2014), 45–51. doi: 10.1007/s10587-014-0081-1
|
| [9] | V. Chvátal, A de Bruijn-Erdős theorem in graphs? In: Graph theory–-favorite conjectures and open problems. 2, Probl. Books in Math., Springer, Cham, 2018, pp. 149–176. |
| [10] | R. Hammack, W. Imrich, S. Klavžar, Handbook of product graphs, 2nd ed., CRC Press, 2011. |
| [11] | W. Imrich, S. Klavžar, Product graphs, structure and recognition, Wiley-Interscience series in discrete mathematics and optimization, Wiley, 2000. |
| [12] |
J. A. Rodríguez-Velázquez, Lexicographic metric spaces: basic properties and the metric dimension, Appl. Anal. Discrete Math., 14 (2020), 20–32. doi: 10.2298/AADM180627004R
|
| [13] | J. A. Rodríguez-Velázquez, Universal lines in graphs. Submitted. |
| [14] | J. A. Rodríguez-Velázquez, Corona metric spaces: basic properties, universal lines, and the metric dimension. Submitted. |
| [15] | M. Ó Searcóid, Metric spaces, Springer Undergraduate Mathematics Series, Springer-Verlag London, Ltd., London, 2007. |
| [16] |
R. Schrader, L. Stenmans, A de Bruijn-Erdős theorem for $(q, q-4)$-graphs, Discrete Appl. Math., 279 (2020), 198–201. doi: 10.1016/j.dam.2019.11.008
|
Figures(1)
Juan Alberto Rodríguez-Velázquez. Solution of the Chen-Chvátal conjecture for specific classes of metric spaces[J]. AIMS Mathematics, 2021, 6(7): 7766-7781. doi: 10.3934/math.2021452
DownLoad: