论文标题
关于圆形弧形的双波动性常数
On the hyperbolicity constant of circular-arc graphs
论文作者
论文摘要
Gromov双曲线是一种有趣的几何特性，因此在几何图的背景下进行研究是很自然的。它从公制的角度测量了图的树木类。特别是，我们对圆形 - 弧形图感兴趣，这是一类重要的几何相交图。在本文中，我们为（有限和无限）圆形ARC图的双曲线常数提供了锐利的边界。此外，我们获得了任何圆形ARC图的补体和线的双曲线常数的边界。为了做到这一点，我们获得了有关常规，和弦和线图的新结果，这些结果本身很有趣。
Gromov hyperbolicity is an interesting geometric property, and so it is natural to study it in the context of geometric graphs. It measures the tree-likeness of a graph from a metric viewpoint. In particular, we are interested in circular-arc graphs, which is an important class of geometric intersection graphs. In this paper we give sharp bounds for the hyperbolicity constant of (finite and infinite) circular-arc graphs. Moreover, we obtain bounds for the hyperbolicity constant of the complement and line of any circular-arc graph. In order to do that, we obtain new results about regular, chordal and line graphs which are interesting by themselves.
