×

Invariant subgraph properties in pseudo-modular graphs. (English) Zbl 0945.05039

Author’s abstract: We prove different invariant subgraph properties for pseudo-modular graphs, and in particular for pseudo-median graphs and ball-Helly graphs. For example we prove that, for any connected interval-finite pseudo-modular graph \(G\) containing no isometric rays or subdivision of an \(\aleph_0\)-regular tree (or \(K_{1,1,\aleph_0}\), resp.): (i) there exists a finite set of vertices of \(G\) that is strictly invariant under every automorphism of \(G\); (ii) any commuting family of certain self-maps called d-faithful (resp. g-faithful) that preserve or collapse the edges (for example functions whose inverse image of each vertex is finite (and which are interval-preserving, resp.)) of \(G\) has a common strictly invariant finite set of vertices. In particular for pseudo-median (resp. ball-Helly) graphs, the invariant finite set of vertices generates an invariant finite regular pseudo-median subgraph (resp. complete subgraph). Moreover the second result holds for ball-Helly graphs, as well as for rayless pseudo-modular graphs, by considering any self-map that preserves or collapses the edges.

MSC:

05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI