论文标题
图形和顶点偏心率的螺旋间隙
Helly-gap of a graph and vertex eccentricities
论文作者
论文摘要
引入了图形Helly-GAP的新的度量参数。图形$ g $称为$α$ - 弱 - 如果任何成对的相交磁盘中的$ g $中的任何系统在每个磁盘的半径增加添加剂值$α$时具有非空的共同交叉点。图$ g $的最低$α$为$α$ - 弱 - 被称为$ g $的helly-gap，并用$α（g）$表示。图$ g $的Helly-gap的特征是Injective Hull $ \ Mathcal {H}（G）$中的距离，这是一个（唯一的）最小Helly图，其中包含$ G $作为等距子绘图。该表征被用作一种工具，以概括许多与Helly图（$α（g）= 0 $）的相关结果，以及弦图（$α（g）\ le 1 $），距离标记图（$α（$α（g）\ le 1 $）和$δ$ -HYPERBIOL GRAPHS（$α$ -HYPERBIOL GRAPHS）（$ to） helly-a-gap $α（g）$。显示了几个其他图形类具有有界的Helly-GAP，包括无限制的图和图形，具有有界的树长度，有界的串联或有界的$α_i$ -metric。
A new metric parameter for a graph, Helly-gap, is introduced. A graph $G$ is called $α$-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 $α$. The minimum $α$ for which a graph $G$ is $α$-weakly-Helly is called the Helly-gap of $G$ and denoted by $α(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 ($α(G)=0$), as well as for chordal graphs ($α(G)\le 1$), distance-hereditary graphs ($α(G)\le 1$) and $δ$-hyperbolic graphs ($α(G)\le 2δ$), to all graphs, parameterized by their Helly-gap $α(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 $α_i$-metric.
