ABSTRACT

The first four chapters of Part III dealt with isometric subgraphs of Cartesian products. We now turn our attention to the strong product. We show that any connected graph isometrically embeds into the strong products of paths, a result that leads naturally to the notion of the strong isometric dimension of a graph. Then we consider special isometric subgraphs of strong products-their retracts-and characterize the weak retracts of strong products of paths as Helly graphs. We close the chapter with a brief overview of other notions of graph dimension that are analogous to the strong isometric dimension.