Computing Truncated Metric Dimension of Trees

Let G = ( V, E ) be a simple, unweighted, connected graph. Let d ( u, v ) denote the distance between vertices u, v . A resolving set of G is a subset S of V such that knowing the distance from a vertex v to every vertex in S uniquely identifies v . The metric dimension of G is defined as the size of the smallest resolving set of G . We define the k -truncated resolving set and k -truncated metric dimension of a graph similarly, but with the notion of distance replaced with d k ( u, v ) := min( d ( u, v ) , k + 1). In this paper, we demonstrate that computing k -truncated dimension of trees is NP-Hard for general k . We then present a polynomial-time algorithm to compute k -truncated dimension of trees when k is a fixed constant.