The Threshold Dimension and Irreducible Graphs
share
Let G be a graph, and let u, v, and w be vertices of G. If the distance between u and w does not equal the distance between v and w, then w is said to resolve u and v. The metric dimension of G, denoted β(G), is the cardinality of a smallest set W of vertices such that every pair of vertices of G is resolved by some vertex of W. The threshold dimension of G, denoted τ(G), is the minimum metric dimension among all graphs H having G as a spanning subgraph. In other words, the threshold dimension of G is the minimum metric dimension among all graphs obtained from G by adding edges. If β(G) = τ(G), then G is said to be irreducible. We 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, we show that every planar graph of order n has threshold dimension O (log_2 n). We show that several infinite families of graphs, known to have metric dimension 3, are in fact irreducible. Finally, we show that for any integers n and b with 1 ≤ b < n, there is an irreducible graph of order n and metric dimension b.
READ FULL TEXT