Minimum Weight Resolving Sets of Grid Graphs

Abstract

For a simple graph $G=(V,E)$ and for a pair of vertices $u,v\in V$, we say that a vertex $w\in V$ resolves $u$ and $v$ if the shortest path from $w$ to $u$ is of a different length than the shortest path from $w$ to $v$. A set of vertices $R\subseteq V$ is a resolving set if for every pair of vertices $u$ and $v$ in $G$, there exists a vertex $w\in R$ that resolves $u$ and $v$. The minimum weight resolving set problem is to find a resolving set $M$ for a weighted graph $G$ such that${\sum }_{v\in M}w(v)$ is minimum, where $w(v)$ is the weight of vertex $v$. In this paper, we explore the possible solutions of this problem for grid graphs $P_n\square P_m$ where $3\le n\le m$. We give a complete characterisation of solutions whose cardinalities are 2 or 3, and show that the maximum cardinality of a solution is $2n-2$. We also provide a characterisation of a class of minimals whose cardinalities range from $4$ to $2n-2$.

21 pages, 10 figures

Cited by in corpus (1)

• An algorithm for the weighted metric dimension of two-dimensional grids