The threshold dimension and irreducible graphs (Q2107754)

The threshold dimension of a graph \(G\) is defined as the minimum metric dimension among all graphs \(H\) having \(G\) as a spanning subgraph. If the threshold dimension of \(G\) equals the metric dimension of \(G\), then \(G\) is said to be irreducible. These notions were introduced in a recent article by the current authors [Discrete Appl. Math. 287, 118--133 (2020; Zbl 1450.05020)]. In this paper, the authors give two upper bounds for the threshold dimension of a graph, the first in terms of the diameter, and the second in terms of the chromatic number. As a consequence, the latter bound implies that the threshold dimension of every planar graph of order \(n\) is less than \(4 \log_{2} n\). It is shown that several infinite families of graphs, known to have metric dimension 3, are in fact irreducible. For example, if \(n \geq 5\), then the generalized Petersen graph \( P(n, 2)\) is irreducible. Finally, the authors proves that for any integers \(n\geq 2\) and \(b\) with \(1 \leq b \leq n-1\), there is a connected irreducible graph of order \(n\) and metric dimension \(b\). Two open questions conclude the paper.