Chen-Chvátal’s conjecture for graphs with restricted girth

Abstract

A classic result in Euclidean geometry asserts that every non-collinear set of n points in the Euclidean plane determines at least n distinct lines. Chen and Chv´atal conjectured that this holds for an arbitrary finite metric space, with an appropriate definition of line. This conjecture remains open even for graph metrics. In this paper, sufficient conditions on the girth to guarantee that a graph satisfies the conjecture are stated. We first study the existence of a universal line generated by an edge. Then, we focus on graphs of order n and maximum girth g with respect to their radius r. We prove that graphs with minimum degree δ ≥ 4 and girth g = 2r+1 or g = 2r have at least n distinct lines and we also partially solve the case when δ = 3. Graphs with cut-vertices are also studied, providing several upper bounds on the diameter, in terms of the girth, in order to assure that the graph satisfies the Chen-Chv´atal conjecture. Finally, we prove that any triangle-free graph of order n, diameter 3 and minimum degree δ ≥ 4 has more than n distinct lines and we also partially solve the case when δ = 3.