Strong geodetic problem in grid like architectures

Abstract

A recent variation of the classical geodetic problem, the strong geodetic problem, is defined as follows. If $G$ is a graph, then $\mathrm{sg}(G)$ is the cardinality of a smallest vertex subset $S$, such that one can assign a fixed geodesic to each pair $\{x,y\}\subseteq S$ so that these $\left(\genfrac{}{}{0ex}{}{|S|}{2}\right)$ geodesics cover all the vertices of $G$. In this paper, the strong geodesic problem is studied on Cartesian product graphs. A general upper bound is proved on the Cartesian product of a path with an arbitrary graph and showed that the bound is tight on flat grids and flat cylinders.