Show simple item record

Authordc.contributor.authorMatamala Vásquez, Martín 
Authordc.contributor.authorZamora, José 
Admission datedc.date.accessioned2020-06-08T23:01:57Z
Available datedc.date.available2020-06-08T23:01:57Z
Publication datedc.date.issued2020
Cita de ítemdc.identifier.citationJ Graph Theory. 2020;1–21.es_ES
Identifierdc.identifier.other10.1002/jgt.22574
Identifierdc.identifier.urihttps://repositorio.uchile.cl/handle/2250/175319
Abstractdc.description.abstractThe line generated by two distinct points, x and y, in a finite metric space M=(V,d), is the set of points given by {z is an element of V:d(x,y)=|d(x,z)+d(z,y)|ord(x,y)=|d(x,z)-d(z,y)|}. It is denoted by xy over bar M. A 2-set {x,y} such that xy over bar M=V is called a universal pair and its generated line a universal line. Chen and Chvatal conjectured that in any finite metric space either there is a universal line, or there are at least |V| different (nonuniversal) lines. Chvatal proved that this is indeed the case when the metric space has distances in the set {0,1,2}. Aboulker et al proposed the following strengthenings for Chen and Chvatal conjecture in the context of metric spaces induced by finite graphs: First, the number of lines plus the number of bridges of the graph is at least the number of points. Second, the number of lines plus the number of universal pairs is at least the number of points of the space. In this study, we prove that the first conjecture is true for bipartite graphs different from C4 or K2,3, and that the second conjecture is true for metric spaces with distances in the set {0,1,2}.es_ES
Patrocinadordc.description.sponsorshipComisión Nacional de Investigación Científica y Tecnológica (CONICYT), CONICYT PIA/BASAL: AFB170001. Comisión Nacional de Investigación Científica y Tecnológica (CONICYT), CONICYT FONDECYT: 1180994.es_ES
Lenguagedc.language.isoenes_ES
Publisherdc.publisherWileyes_ES
Type of licensedc.rightsAttribution-NonCommercial-NoDerivs 3.0 Chile*
Link to Licensedc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/cl/*
Sourcedc.sourceJournal of Graph Theoryes_ES
Keywordsdc.subjectChen‐Chvátal conjecturees_ES
Keywordsdc.subjectGraph metrices_ES
Títulodc.titleLines in bipartite graphs and in 2-metric spaceses_ES
Document typedc.typeArtículo de revistaes_ES
dcterms.accessRightsdcterms.accessRightsAcceso Abierto
Catalogueruchile.catalogadorrvhes_ES
Indexationuchile.indexArtículo de publicación ISI
Indexationuchile.indexArtículo de publicación SCOPUS


Files in this item

Icon

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivs 3.0 Chile
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 Chile