A New Class of Graphs That Satisfies the Chen‐Chvátal Conjecture

A well‐known combinatorial theorem says that a set of n non‐collinear points in the plane determines at least n distinct lines. Chen and Chvátal conjectured that this theorem extends to metric spaces, with an appropriated definition of line. In this work, we prove a slightly stronger version of Chen...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2018-01, Vol.87 (1), p.77-88
Main Authors: Aboulker, P., Matamala, M., Rochet, P., Zamora, J.
Format: Article
Language:English
Subjects:
Chen‐Chvatal conjecture
Combinatorial analysis
graphe metric
Graphs
Theorems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A well‐known combinatorial theorem says that a set of n non‐collinear points in the plane determines at least n distinct lines. Chen and Chvátal conjectured that this theorem extends to metric spaces, with an appropriated definition of line. In this work, we prove a slightly stronger version of Chen and Chvátal conjecture for a family of graphs containing chordal graphs and distance‐hereditary graphs.
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.22142