Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:
| Indexado |
|
||||
| DOI | 10.1016/J.PROCS.2023.08.247 | ||||
| Año | 2023 | ||||
| Tipo | proceedings paper |
Citas Totales
Autores Afiliación Chile
Instituciones Chile
% Participación
Internacional
Autores
Afiliación Extranjera
Instituciones
Extranjeras
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.
| Ord. | Autor | Género | Institución - País |
|---|---|---|---|
| 1 | Araujo-Pardo, Gabriela | - |
Universidad Nacional Autónoma de México - México
Univ Nacl Autonoma Mexico - México |
| 2 | Matamala, Martín | Hombre |
Universidad de Chile - Chile
|
| 3 | ZAMORA-PONCE, JOSE TOMAS | Hombre |
Universidad Nacional Andrés Bello - Chile
|
| 4 | Fernandes, C | - | |
| 5 | Rajsbaum, S | - |
| Fuente |
|---|
| PAPIIT-UNAM |
| Direccion General de Asuntos del Personal Academico, Universidad Nacional Autonoma de Mexico |
| MathAmsud |
| Agencia Nacional de Investigación y Desarrollo |
| ANID Basal Program |
| Agradecimiento |
|---|
| ✩ Supported by ANID Basal program FB21005, MathAmSud MATH210008 and PAPIIT-UNAM grant IN108121. ✩ Supported by ANID Basal program FB21005, MathAmSud MATH210008 and PAPIIT-UNAM grant IN108121. |
| Supported by ANID Basal program FB21005, MathAmSud MATH210008 and PAPIIT-UNAM grant IN108121. |