On constructible graphs, locally Helly graphs, and convexity
On constructible graphs, locally Helly graphs, and convexity
复制标题
关于可构造图、局部 Helly 图和凸性
DOI：
10.1002/jgt.10120
复制
发表时间：
2003
影响因子：
0.9
通讯作者：
N. Polat
中科院分区：
文献类型：
--
作者：
N. Polat
如果存在良好的顶点≤≤，则A（有限或无限）图G是可构造的X具有Z <X的X。 Helly如果对于距离为d≥2的G的每个对（x，y）的顶点（x，y），则存在一个顶点，其距离x的距离为d -1，并且与y相邻，并且与y的所有邻居相邻，其距离与x的距离最多是d那是当地的Helly Graph G是有限的Helly，也就是说，G的每个有限的非分离球的家族都有非空的相交，我们通过禁止的子图提供了足够的条件。最终的Helly图是等效的，最终概括了不同的结果，尤其如果ω（g）是有限的，则构造图G中的构造凸的数字h（g）等于其集团数ω（g）。 2003
A (finite or infinite) graph G is constructible if there exists a well‐ordering ≤ of its vertices such that for every vertex x which is not the smallest element, there is a vertex y < x which is adjacent to x and to every neighbor z of x with z < x. Particular constructible graphs are Helly graphs and connected bridged graphs. In this paper we study a new class of constructible graphs, the class of locally Helly graphs. A graph G is locally Helly if, for every pair (x,y) of vertices of G whose distance is d ≥ 2, there exists a vertex whose distance to x is d − 1 and which is adjacent to y and to all neighbors of y whose distance to x is at most d. Helly graphs are locally Helly, and the converse holds for finite graphs. Among different properties we prove that a locally Helly graph is strongly dismantable, hence cop‐win, if and only if it contains no isometric rays. We show that a locally Helly graph G is finitely Helly, that is, every finite family of pairwise non‐disjoint balls of G has a non‐empty intersection. We give a sufficient condition by forbidden subgraphs so that the three concepts of Helly graphs, of locally Helly graphs and of finitely Helly graphs are equivalent. Finally, generalizing different results, in particular those of Bandelt and Chepoi 1 about Helly graphs and bridged graphs, we prove that the Helly number h(G) of the geodesic convexity in a constructible graph G is equal to its clique number ω(G), provided that ω(G) is finite. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 280–298, 2003