Obstructions to a small hyperbolicity in Helly graphs

Abstract

It is known that for every graph $G$ there exists the smallest Helly graph $\mathcal{H}(\mathcal{G})$ into which $G$ isometrically embeds ($\mathcal{H}(\mathcal{G})$ is called the injective hull of $G$) such that the hyperbolicity of $\mathcal{H}(\mathcal{G})$ is equal to the hyperbolicity of $G$. Motivated by this, we investigate structural properties of Helly graphs that govern their hyperbolicity and identify three isometric subgraphs of the King-grid as structural obstructions to a small hyperbolicity in Helly graphs.

18 pages, 16 figures

Cited by in corpus (2)

• Helly groups
• First-order logic axiomatization of metric graph theory