Search

Let G be a connected graph with vertex set V , where the distance between two vertices is the length of a shortest path between them. A set S ⊆ V is [ 1 , 2 ] -resolving if each vertex of G is at most distance-two away from a vertex in S and, given a pair of distinct vertices not in S , either there is a vertex in S adjacent to exactly one member of the given pair, or there are two vertices in S each of which is distance-two from exactly one member of the given pair. The [ 1 , 2 ] -dimension of G is the minimum cardinality of a [ 1 , 2 ] -resolving set of G. In this paper, we study the [ 1 , 2 ] -dimension of graphs by proving that the [ 1 , 2 ] -dimension problem is an NP-complete problem, and determine the [ 1 , 2 ] -dimension of some classes of graphs, such as paths, cycles, and full k -ary trees. We also introduce a generalization of metric dimension of which the (original) metric dimension and the [ 1 , 2 ] -dimension, as well as other metric dimension variants in the literature, are special instances. [ABSTRACT FROM AUTHOR]