Retract‐collapsible graphs and invariant subgraph properties
作者:
Norbert Polat,
期刊:
Journal of Graph Theory
(WILEY Available online 1995)
卷期:
Volume 19,
issue 1
页码: 25-44
ISSN:0364-9024
年代: 1995
DOI:10.1002/jgt.3190190105
出版商: Wiley Subscription Services, Inc., A Wiley Company
数据来源: WILEY
摘要:
AbstractA (finite or infinite) graphGis 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 ofG, 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, ifGis a subretract‐collapsible graph, andfa contraction fromGintoG, then (i) ifGhas no infinite simplices, thenf(S) =Sfor some simplexSofG; and (ii) if the dismantling ofGcan be achieved in a finite number of steps and if some family of simplices ofGhas a compacity property, then there is a simplexSofGsuch thatf(S) ⊆S. This last result generalizes a property of bounded ball‐Helly graphs. © 1995
点击下载:
PDF
(983KB)
返 回