On isometric subgraphs of infinite bridged graphs and geodesic convexity
type: Item
instance of: scholarly article
title: On isometric subgraphs of infinite bridged graphs and geodesic convexity
zbMATH Open document ID: 0995.05045
DOI: 10.1016/S0012-365X(01)00097-8
author: Norbert Polat
published in: Discrete Mathematics
publication date: 2002-05-21T00:00:00Z
review text: 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\).
reviewed by: Ioan Tomescu
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 1743038
zbMATH Keywords: infinite graph
zbMATH Keywords: isometric subgraph
zbMATH Keywords: geodesic convexity
zbMATH Keywords: bridged graph
zbMATH Keywords: constructible graph
zbMATH Keywords: dominated vertex
zbMATH Keywords: discrete deformation retract
zbMATH Keywords: strong dismantlable graph
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1743038