Premium
Retract‐collapsible graphs and invariant subgraph properties
Author(s) -
Polat Norbert
Publication year - 1995
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190190105
Subject(s) - mathematics , combinatorics , retract , induced subgraph , bounded function , simplex , vertex (graph theory) , graph factorization , graph , discrete mathematics , line graph , graph power , pure mathematics , mathematical analysis
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.