Retract-collapsible graphs and invariant subgraph properties
Retract-collapsible graphs and invariant subgraph properties
复制标题
收缩折叠图和不变子图属性
DOI：
10.1002/jgt.3190190105
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
N. Polat
中科院分区：
文献类型：
--
作者：
N. Polat
如果可以通过系统地删除严格统治的每个顶点，以使其余的子图是G的缩回，并且可以获得A，则（有限或无限）图G是缩回的。如果在每个顶点上种植一些无射线的树，则在末尾进行了单个图形。 COP-WIN；仅当它没有等距的无限路径时，且含量的图形是可依靠的（因此，如果它没有无限的路径，或者是有界的）。特别是，如果g是一个可逆转的图形，而f从g到g的收缩，则（i）如果G没有无限的简单，则对于g的某些单纯形，f（s）= s； G的拆除可以是在有限数量的步骤中实现，如果某些g的简单家族具有紧凑型特性，则有一个单纯的g，使得f（s）⊆S。这个最后的结果概括了有界球壳图的属性。 ©1995 John Wiley＆Sons，Inc。
A (finite or infinite) graph G is retract-collapsible if it can be dismantled by deleting systematically at each step every vertex that is strictly dominated, in such a way that the remaining subgraph is a retract of G, and so as to get a simplex at the end. A graph is subretract-collapsible if some graph obtained by planting some rayless tree at each of its vertices is retract-collapsible. It is shown that the subretract-colapsible graphs are cop-win; and that a ball-Helly graph is subretract-collapsible if and only if it has no isometric infinite paths (thus in particular if it has no infinite paths, or if it is bounded). Several fixed subgraph properties are proved. In particular, if G is a subretract-collapsible graph, and f a contraction from G into G, then (i) if G has no infinite simplices, then f(S) = S for some simplex S of G; and (ii) if the dismantling of G can be achieved in a finite number of steps and if some family of simplices of G has a compacity property, then there is a simplex S of G such that f(S) ⊆ S. This last result generalizes a property of bounded ball-Helly graphs. © 1995 John Wiley & Sons, Inc.