TY - JOUR

T1 - Lines in bipartite graphs and in 2-metric spaces

AU - Matamala, Martín

AU - Zamora, José

N1 - Funding Information:
This study was partially supported by Basal program AFB170001 and CONICYT Fondecyt/Regular 1180994.

PY - 2020/1/1

Y1 - 2020/1/1

N2 - The line generated by two distinct points, x and y, in a finite metric space M = (V, d), is the set of points given by (Formula presented.) It is denoted by (Formula presented.). A 2-set {x,y} such that (Formula presented.) is called a universal pair and its generated line a universal line. Chen and Chvátal conjectured that in any finite metric space either there is a universal line, or there are at least |V| different (nonuniversal) lines. Chvátal 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 Chvátal 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}.

AB - The line generated by two distinct points, x and y, in a finite metric space M = (V, d), is the set of points given by (Formula presented.) It is denoted by (Formula presented.). A 2-set {x,y} such that (Formula presented.) is called a universal pair and its generated line a universal line. Chen and Chvátal conjectured that in any finite metric space either there is a universal line, or there are at least |V| different (nonuniversal) lines. Chvátal 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 Chvátal 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}.

KW - Chen-Chvátal conjecture

KW - graph metric

UR - http://www.scopus.com/inward/record.url?scp=85084226856&partnerID=8YFLogxK

U2 - 10.1002/jgt.22574

DO - 10.1002/jgt.22574

M3 - Article

AN - SCOPUS:85084226856

SN - 0364-9024

VL - 95

SP - 565

EP - 585

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 4

ER -