Minimal Resolving Sets in Rectangular Grid Graphs: A Complete Characterization and Enumeration
Abstract
Let m,n ≥ 3. A set of vertices S of the rectangular grid graph Pm □ Pn is resolving if the taxicab distance vectors of the vertices of Pm □ Pn with respect to S are pairwise distinct. A resolving set S is minimal if no proper subset of S is resolving, and a minimal resolving set of cardinality k is called a k-minimal. We extend the work of Andersen et al., who characterized $3$-minimals, established the maximum cardinality 2min(m,n)−2, and posed the complete characterization and enumeration of minimal resolving sets for grids as an open problem, and Adar and Epstein, who showed that $3$ is the only possible odd cardinality and that every minimal resolving set of cardinality at least $4$ can be ordered to form a sequence corresponding to a zigzag sequence. We provide a recursive construction that generates exactly the minimal resolving sets of cardinality at least $4$ for grids. We derive from the construction closed-form formulas to enumerate the k-minimals for all even 4 ≤ k ≤ 2min(m,n) −2. Together with the known characterizations for cardinalities $2$ and $3$ and a direct enumeration of the $3$-minimals, this yields a complete characterization and enumeration of the minimal resolving sets of rectangular grid graphs of every possible cardinality.
Related
- Groups satisfying the minimal condition on centralizers are complete co-analytic
- Complete non-orientable minimal surfaces of finite total curvature: Approximation and interpolation
- A complete classification of minimal value set polynomials
- Conformal structures and rigidity of complete stable minimal hypersurfaces
- Index estimates for complete noncompact free boundary minimal surfaces
BibTeX
@misc{huang2026minimal,
title = {{Minimal Resolving Sets in Rectangular Grid Graphs: A Complete Characterization and Enumeration}},
author = {Caroline Huang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.35896},
eprint = {2609.35896},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35896},
}
RIS
TY - UNPB
TI - Minimal Resolving Sets in Rectangular Grid Graphs: A Complete Characterization and Enumeration
AU - Caroline Huang
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.35896
UR - https://arxiv.org/abs/2609.35896
AB - Let m,n ≥ 3. A set of vertices S of the rectangular grid graph P_m □ P_n is resolving if the taxicab distance vectors of the vertices of P_m □ P_n with respect to S are pairwise distinct. A resolving set S is minimal if no proper subset of S is resolving, and a minimal resolving set of cardinality k is called a k-minimal. We extend the work of Andersen et al., who characterized $3$-minimals, established the maximum cardinality 2min(m,n)−2, and posed the complete characterization and enumeration of minimal resolving sets for grids as an open problem, and Adar and Epstein, who showed that $3$ is the only possible odd cardinality and that every minimal resolving set of cardinality at least $4$ can be ordered to form a sequence corresponding to a zigzag sequence. We provide a recursive construction that generates exactly the minimal resolving sets of cardinality at least $4$ for grids. We derive from the construction closed-form formulas to enumerate the k-minimals for all even 4 ≤ k ≤ 2min(m,n) −2. Together with the known characterizations for cardinalities $2$ and $3$ and a direct enumeration of the $3$-minimals, this yields a complete characterization and enumeration of the minimal resolving sets of rectangular grid graphs of every possible cardinality.
ER -