A De Bruijn–Erdős Theorem for Chordal Graphs
The Electronic Journal of Combinatorics2015Vol. 22(1)
Citations Over TimeTop 10% of 2015 papers
Laurent Beaudou, Adrian Bondy, Xiaohong Chen, Ehsan Chiniforooshan, Maria Chudnovsky, Vašek Chvátal, Nicolás Fraiman, Yori Zwólš
Abstract
A special case of a combinatorial theorem of De Bruijn and Erdős asserts that every noncollinear set of $n$ points in the plane determines at least $n$ distinct lines. Chen and Chávtal suggested a possible generalization of this assertion in metric spaces with appropriately defined lines. We prove this generalization in all metric spaces induced by connected chordal graphs.
Related Papers
- → Assertion: New Philosophical Essays(2011)186 cited
- → Cryptographically Strong de Bruijn Sequences with Large Periods(2013)35 cited
- → A recursive construction of nonbinary de Bruijn sequences(2010)23 cited
- → A new digraphs composition with applications to de Bruijn and generalized de Bruijn digraphs(1997)7 cited
- → Construction of De Bruijn Sequences from l-sequences(2021)2 cited