Weak geodesic topology and fixed finite subgraph theorems in infinite partial cubes II. Fixed subgraph properties and infinite treelike partial cubes

详细信息    查看全文

• 作者：Norbert Polat^a ;   ; ^{norbert.polat@univ-lyon3.fr}
• 关键词：Weak geodesic topology ; Partial cube ; Netlike partial cube ; Treelike partial cube ; Isometric ray ; Divergent ray ; Fixed subgraph theorem ; Contraction ; Automorphism ; Translating self-contraction
• 刊名：Discrete Mathematics
• 出版年：2012
• 出版时间：6 January 2012
• 年：2012
• 卷：312
• 期：1
• 页码：61-73
• 全文大小：295 K

文摘

We prove that if a partial cube contains no divergent rays, then: (i)?there exists a non-empty finite convex subgraph of which is fixed by every automorphism of ; (ii)?every self-contraction of fixes a non-empty finite isometric subgraph of ; (iii)?for every commuting family of self-contractions of , there exists a non-empty finite isometric subgraph of which is fixed by every element of . Moreover, we show that those fixed subgraphs can be specified for some particular partial cubes, as is the case for median graphs and more generally for netlike partial cubes. We give new examples of such special graphs by extending the finite concept of treelike partial cubes [B. Bre?ar et?al., Tree-like isometric subgraphs of hypercubes, Discussiones Mathematicae¨CGraph Theory 23 (2003), 227?40] to the infinite case, and by introducing what we call faithful-treelike, convex-treelike and strongly treelike partial cubes.