[1,2]-dimension of graphs

Fei Huang Chang, Ma Lian Chia, David Kuo, Sheng Chyang Liaw, Yi Xuan Lin

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)232-245
Number of pages14
JournalDiscrete Applied Mathematics
StatePublished - 15 Oct 2023


  • Full k-ary tree
  • NP-complete
  • [1,2]-basis
  • [1,2]-dimension
  • [1,2]-resolving set


Dive into the research topics of '[1,2]-dimension of graphs'. Together they form a unique fingerprint.

Cite this