The Chen-Chvátal conjecture for metric spaces induced by distance-hereditary graphs

DOI10.1016/J.EJC.2014.06.009zbMATH Open1301.05093arXiv1312.3214OpenAlexW2093180783WikidataQ122900347 ScholiaQ122900347MaRDI QIDQ458577FDOQ458577

Rohan Kapadia, Pierre Aboulker

Publication date: 8 October 2014

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: A special case of a theorem of De Bruijn and ErdH{o}s asserts that any noncollinear set of $n$ points in the plane determines at least $n$ distinct lines. Chen and Chv'atal conjectured a generalization of this result to arbitrary finite metric spaces, with a particular definition of lines in a metric space. We prove it for metric spaces induced by connected distance-hereditary graphs -- a graph $G$ is called distance-hereditary if the distance between two vertices $u$ and $v$ in any connected induced subgraph $H$ of $G$ is equal to the distance between $u$ and $v$ in $G$.

Full work available at URL: https://arxiv.org/abs/1312.3214

zbMATH Keywords

connected distance-hereditary graphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Connectivity (05C40)

Cites Work

• Distance-hereditary graphs
• Title not available (Why is that?)
• A de Bruijn-Erdős theorem for chordal graphs
• Lines in hypergraphs
• Number of lines in hypergraphs
• A de Bruijn-Erdős theorem for 1–2 metric spaces
• Lines, betweenness and metric spaces
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• A de Bruijn - Erd\H{o}s theorem and metric spaces
• Problems related to a de Bruijn-Erdös theorem

Cited In (14)

• A de Bruijn-Erdős theorem for \((q,q-4)\)-graphs
• De Bruijn-Erdős-type theorems for graphs and posets
• A New Class of Graphs That Satisfies the Chen‐Chvátal Conjecture
• Solution of the Chen-Chvátal conjecture for specific classes of metric spaces
• Universal lines in graphs
• Lines in bipartite graphs and in 2‐metric spaces
• Metric subgraphs of the chamfer metrics and the Melter-Tomescu path generated metrics
• Chen and Chvátal's conjecture in tournaments
• Lines, betweenness and metric spaces
• Chen-Chvátal’s conjecture for graphs with restricted girth
• Graphs with no induced house nor induced hole have the de Bruijn–Erdös property
• Lines in the plane with the \(L_1\) metric
• Betweenness structures of small linear co-size
• Number of lines in hypergraphs

This page was built for publication: The Chen-Chvátal conjecture for metric spaces induced by distance-hereditary graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q458577)