The threshold strong dimension of a graph

Abstract Let G be a connected graph and u , v and w vertices of G . Then w is said to strongly resolve u and v , if there is either a shortest u - w path that contains v or a shortest v - w path that contains u . A set W of vertices of G is a strong resolving set if every pair of vertices of G is strongly resolved by some vertex of W . A smallest strong resolving set of a graph is called a strong basis and its cardinality, denoted β s ( G ) , the strong dimension of G . The threshold strong dimension of a graph G , denoted τ s ( G ) , is the smallest strong dimension among all graphs having G as spanning subgraph. A graph whose strong dimension equals its threshold strong dimension is called β s -irreducible. In this paper we establish a geometric characterization for the threshold strong dimension of a graph G that is expressed in terms of the smallest number of paths (each of sufficiently large order) whose strong product admits a certain type of embedding of G . We demonstrate that the threshold strong dimension of a graph is not equal to the previously studied threshold dimension of a graph. Graphs with strong dimension 1 and 2 are necessarily β s -irreducible. It is well-known that the only graphs with strong dimension 1 are the paths. We completely describe graphs with strong dimension 2 in terms of the strong resolving graphs introduced by Oellermann and Peters-Fransen. We obtain sharp upper bounds for the threshold strong dimension of general graphs and determine exact values for this invariant for certain subclasses of trees.