The threshold dimension of a graph (Q2004085)

In this paper, the threshold dimension of a graph \(G\), denoted by \(\tau (G)\) is defined as the minimum metric dimension among all graphs \(H\) having \(G\) as a spanning subgraph, or the minimum metric dimension among all graphs obtained from \(G\) by adding edges. If \(\beta (G)= \tau (G)\), where \(\beta (G)\) denotes the metric dimension of \(G\), then \(G\) is said to be irreducible; otherwise, \(G\) is called reducible. If \(H\) is a graph having \(G\) as a spanning subgraph and such that \(\beta (H)=\tau (G)\), then \(H\) is called a threshold graph of \(G\). The first part of this paper gives an expression for the threshold dimension of a graph in terms of a minimum number of strong products of paths (each of sufficiently large order) that admits a certain type of embedding of the graph. Using this result, it is proved that there are trees of arbitrarily large metric dimension having threshold dimension equal to two. The second part of the paper focuses on the threshold dimension of trees, establishing a sharp upper bound for the threshold dimension of trees and showing that irreducible trees are precisely those of metric dimension at most 2. Moreover, if \(T\) is a tree with metric dimension 3 or 4, then \(T\) has threshold dimension 2 and in each of these two cases a threshold graph for \(T\) can be obtained by adding exactly one or two edges to \(T\), respectively but there are trees of metric dimension 5 with threshold dimension exceeding 2. Two open problems conclude the paper.