The Metric Dimension of Two-Dimensional Extended Meshes

  • Ron Adar
  • Leah Epstein


We consider two-dimensional grids with diagonals, also called extended meshes or meshes. Such a graph consists of vertices of the form (i, j) for 1 ≤ i ≤ m and 1 ≤ j ≤ n, for given m, n ≥ 2. Two vertices are defined to be adjacent if the `∞ distance between their vectors is equal to 1. A landmark set is a subset of vertices L ⊆ V , such that for any distinct pair of vertices u, v ∈ V , there exists a vertex of L with different distances to u and v. We analyze the metric dimension and show how to obtain a landmark set of minimum cardinality.
How to Cite
Adar, R., & Epstein, L. (2018). The Metric Dimension of Two-Dimensional Extended Meshes. Acta Cybernetica, 23(3), 761-772.
Regular articles