A characterization of graphs of diameter two with fewer lines than vertices
Martín Matamala · 2025
Read A characterization of graphs of diameter two with fewer lines than vertices by Martín Matamala (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-19601.txt.
Description
Martín Matamala settles a graph case of a conjecture about lines in metric spaces. In 2008 Chen and Chvátal guessed that any metric space on n points determines at least n distinct lines, unless every point lies on a single line. Chvátal had already confirmed the guess for spaces whose distances take only the values zero, one, and two.
Matamala looks at metric spaces coming from graphs of diameter two, where the same distance restriction holds. He proves there is a family of exactly ten graphs with a clean property: such a space has fewer lines than points precisely when its graph belongs to that family. The result pins down all the exceptional cases for this class.
Catalog record
| CREATOR | Martín Matamala |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-19601