Metric properties of locally connected graphs.

Abstract: A set of n points in the plane which are not all collinear defines at least n distinct lines. In 2008, Chen and Chvátal conjectured that this property holds for all finite metric spaces. This conjecture is still open, even for metric spaces induced by graphs. In this talk, we show that locally connected graphs satisfy this property and an even stronger one.

Posted on Nov 21, 2024 in Seminario de Grafos, Seminars