On isometric subgraphs of infinite bridged graphs and geodesic convexity Original Research Article

A subgraph H of a graph G is 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 (geodesically) convex if it contains all vertices of every shortest path joining vertices in K. In this paper we investigate some properties of the isometric subgraphs of an infinite bridged graph G containing no infinite simplices (i.e., complete subgraphs), and in particular of those whose vertex sets are convex in G. We prove 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 we show 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, we deduce that for every convex set K in G, there is an enumeration (xα)α<σ of the vertices of G−K such that, for every α<σ, xα is dominated in the subgraph of G induced by {xβ: α⩽β<σ}∪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.