On isometric subgraphs of infinite bridged graphs and geodesic convexity
A subgraph \(H\) of a graph \(G\) is said to be isometric if the distance between any pair of vertices in \(H\) is the same as that in \(G\). A subset \(K\) of the vertex set of a graph \(G\) is said to be (geodesically) convex if it contains all vertices of every shortest path joining vertices in \(K\). In this paper some properties of the isometric subgraphs of an infinite bridged graph \(G\) containing no infinite simplices (i.e., complete subgraphs) are investigated, and in particular of those whose vertex sets are convex in \(G\). It is proved that every finite set of vertices of \(G\) is contained in a finite isometric subgraph of \(G\). Several results highlight the important role played by the dominated vertices of \(G\) (a vertex \(x\) is dominated by a vertex \(y\) if \(y\) is adjacent to \(x\) and to all neighbors of \(x\)). In particular it is shown that \(G\) is finite whenever the set \(D(G)\) of its dominated vertices is finite. If, however, every ray of \(G\) contains an infinite bounded subset, then \(V(G)\) is the convex hull of \(D(G)\). From this, it is deduced that for every convex set \(K\) in \(G\), there is an enumeration \((x_{\alpha })_{\alpha <\sigma }\) of the vertices of \(G-K\) such that, for every \(\alpha <\sigma \), \(x_{\alpha }\) is dominated in the subgraph of \(G\) induced by \(\{x_{\beta}: \alpha \leq \beta <\sigma \}\cup K\). Finally, if, in addition, \(G\) is bounded, then every subgraph whose vertex set is convex in \(G\) is a (discrete) deformation retract of \(G\).
scientific article; zbMATH DE number 1743038