The Threshold Dimension and Threshold Strong Dimension of a Graph: A Survey

Let G be a connected graph and u, v and w vertices of G. Then w is said to resolve u and v if the distance from u to w does not equal the distance from v to w. If there is either a shortest u-w path that contains v or a shortest v-w path that contains u, then we say that w strongly resolves u and v. A set W of vertices of G is a resolving set (strong resolving set), if every pair of vertices of G is resolved (respectively, strongly resolved) by some vertex of W. A smallest resolving set (strong resolving set) of a graph is called a basis (respectively, a strong basis) and its cardinality, denoted β(G) (respectively, βs(G)), the metric dimension (respectively, the strong dimension) of G. The threshold dimension (respectively, threshold strong dimension) of a graph G, denoted τ(G) (respectively, τs(G)), is the smallest metric dimension (respectively, strong dimension) among all graphs having G as a spanning subgraph. We survey results on the threshold dimension and threshold strong dimension and contrast these invariants. The paper concludes with several open problems for these parameters.