TOPICS
Search

Minimal Resolving Set

A minimal resolving set of a graph is a resolving set that contains no proper subset that is also a resolving set. Thus minimality is by inclusion and does not imply that the set has minimum cardinality. A minimal resolving set of cardinality k is called a k-minimal.

The maximum cardinality of a minimal resolving set of a graph G is called its upper dimension and is denoted dim^+(G) (Chartrand et al. 2000). Enumerating the minimal resolving sets of general graphs is equivalent to enumerating the minimal transversals of hypergraphs (Bergougnoux et al. 2025).

For rectangular grid graphs P_m square P_n with m,n>=3, Melter and Tomescu (1984) characterized the metric bases, equivalently the 2-minimals. Andersen et al. (2016) characterized the 3-minimals and proved that the upper dimension is 2min(m,n)-2. Adar and Epstein (2016) proved that 3 is the only possible odd cardinality and that every minimal resolving set of cardinality at least 4 can be ordered to correspond to a zigzag sequence.

Building on these results, Huang (2026) completely characterized and enumerated the minimal resolving sets of every such grid graph. Such a graph has k-minimals exactly for

k in {2,3} union {2r:2<=r<=min(m,n)-1}.

In particular, 3 is the only possible odd cardinality and the maximum cardinality is 2min(m,n)-2. For 3<=r<=min(m,n)-1, the number of 2r-minimals is

N_(2r)(m,n)=1/r[(m+3r-1)(m+r-2; 2r-1)(n+r-3; 2r-2)+(n+3r-1)(n+r-2; 2r-1)(m+r-3; 2r-2)].

Huang also gave closed formulas for the cases k=2, 3, and 4 and a recursive construction that generates exactly all minimal resolving sets of cardinality at least 4.

See also

Grid Graph, Metric Dimension

Explore with Wolfram|Alpha

References

Adar, R. and Epstein, L. "An Algorithm for the Weighted Metric Dimension of Two-Dimensional Grids." 18 Feb 2016. https://arxiv.org/abs/1602.05899.Andersen, P. J.; Grigorious, C.; and Miller, M. "Minimum Weight Resolving Sets of Grid Graphs." Disc. Math. Algorithms Appl. 8, 1650048, 2016. https://doi.org/10.1142/S1793830916500488.Bergougnoux, B.; Defrain, O.; and Mc Inerney, F. "Enumerating Minimal Solution Sets for Metric Graph Problems." Algorithmica 87, 712-735, 2025. https://doi.org/10.1007/s00453-025-01300-4.Chartrand, G.; Poisson, C.; and Zhang, P. "Resolvability and the Upper Dimension of Graphs." Comput. Math. Appl. 39, 19-28, 2000. https://doi.org/10.1016/S0898-1221(00)00126-7.Huang, C. "Minimal Resolving Sets in Rectangular Grid Graphs: A Complete Characterization and Enumeration." 27 Sep 2026. https://arxiv.org/abs/2609.35896.Melter, R. A. and Tomescu, I. "Metric Bases in Digital Geometry." Comput. Vis. Graph. Image Process. 25, 113-121, 1984. https://doi.org/10.1016/0734-189X(84)90051-3.

Cite this as:

Weisstein, Eric W. "Minimal Resolving Set." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MinimalResolvingSet.html

Subject classifications