首页   按字顺浏览 期刊浏览 卷期浏览 Retract‐collapsible graphs and invariant subgraph properties
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)



返 回