7 papers · 1 filter
Chen-Chvátal Conjecture for Graphs of Diameter 3
MartÃn Matamala, Luciano Villarroel-Sepúlveda
In 2008, Chen and Chvátal conjectured that in every finite metric space of points, there are at least distinct lines, or the whole set of points is a line. This is a gener…
A characterization of graphs of diameter two with fewer lines than vertices
MartÃn Matamala
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…
A characterization of locally ordered ternary relations in terms of digraphs
Guillermo Gamboa Quintero, MartÃn Matamala, Juan Pablo Peña
In 1917, Huntington and Kline, followed by Huntington in 1924, studied systems of axioms for ternary relations aiming to capture the concepts of linear order (called betwenness) an…
Locally connected graphs: metric properties
MartÃn Matamala, Juan Pablo Peña, José Zamora
In this work we show that any connected locally connected graph defines a metric space having at least as many lines as vertices with only three exception: the complete multipartit…
Weighted Cages
G. Araujo-Pardo, C. De la Cruz, M. Matamala +1
Cages (-regular graphs of girth and minimum order) and their variants have been studied for over seventy years. Here we propose a new variant, "weighted cages". We character…
Lines on digraphs of low diameter
Gabriela Araujo-Pardo, MartÃn Matamala, Juan P. Peña +1
A set of n non-collinear points in the Euclidean plane defines at least n different lines. Chen and Chvtal in 2008 conjectured that the same results is true in metric spaces for an…