The Threshold Dimension and Irreducible Graphs

Abstract

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.

Keywords

• threshold dimension
• metric dimension
• distance in graphs
• 05c12
• 05c69