Helly-gap of a graph and vertex eccentricities

Abstract

A new metric parameter for a graph, Helly-gap, is introduced. A graph $G$ is called $\alpha$-weakly-Helly if any system of pairwise intersecting disks in $G$ has a nonempty common intersection when the radius of each disk is increased by an additive value $\alpha$. The minimum $\alpha$ for which a graph $G$ is $\alpha$-weakly-Helly is called the Helly-gap of $G$ and denoted by $\alpha (G)$. The Helly-gap of a graph $G$ is characterized by distances in the injective hull $\mathcal{H}(G)$, which is a (unique) minimal Helly graph which contains $G$ as an isometric subgraph. This characterization is used as a tool to generalize many eccentricity related results known for Helly graphs ($\alpha (G)=0$), as well as for chordal graphs ($\alpha (G)\le 1$), distance-hereditary graphs ($\alpha (G)\le 1$) and $\delta$-hyperbolic graphs ($\alpha (G)\le 2\delta$), to all graphs, parameterized by their Helly-gap $\alpha (G)$. Several additional graph classes are shown to have a bounded Helly-gap, including AT-free graphs and graphs with bounded tree-length, bounded chordality or bounded ${\alpha }_i$-metric.

21 pages, 7 figures