Counting lines in semi-complete digraphs∗

Gabriela Araujo-Pardo, Martín Matamala, José Zamora

Producción científica: Contribución a una revistaArtículo de la conferenciarevisión exhaustiva

Resumen

A digraph D = (V, A) is semi-complete if for each pair of distinct vertices x and y in V, either xy or yx belong to A. A subset of vertices is a line of D if there are two distinct vertices x and y such that for any vertex z ϵ V, z ϵ if and only if a directed shortest path exists containing x, y and z. A classic result proved by Erdös says that any set of n points in the Euclidean plane endowed with the Euclidean distance defines a metric space with at least n different lines unless there is a line containing the n points. Chen and Chvátal in 2008 conjectured that the same results is true for any metric spaces where lines are defined in a manner similar to above. In this paper we prove that in any semi-complete digraphs with n vertices the number of lines defined by vertices connected by an arc is at least n. Then, the quasi-metric spaces defined by semi-complete digraphs fulfill Chen and Chvátal conjecture in a stronger manner as, on the one hand, they always have at least n lines, and on the other hand, these n lines are defined by vertices at distance one.

Idioma originalInglés
Páginas (desde-hasta)352-359
Número de páginas8
PublicaciónProcedia Computer Science
Volumen223
DOI
EstadoPublicada - 2023
Evento12th Latin-American Algorithms, Graphs and Optimization Symposium, LAGOS 2023 - Huatulco, México
Duración: 18 sep. 202322 sep. 2023

Áreas temáticas de ASJC Scopus

  • Ciencia de la Computación General

Citar esto