The metric dimension
(Tillquist et al. 2021) or (Tomescu and Javid 2007, Ali et al. 2016) of a
graph
is the smallest number of nodes required to identify all other nodes based on shortest
path distances uniquely. More explicitly, following Foster-Greenwood and Uhl (2022),
let
be a finite connected graph with vertex
set .
For vertices ,
the graph distance is the length of the shortest path between and in . Consider a subset of vertices and refer to the vertices in as "landmarks." Then is called a resolving set if, for every pair of distinct vertices
, there exists a landmark such that . A resolving set of smallest possible size is
called a metric basis for , and the metric dimension of is the size of a metric basis.

Tillquist et al. (2021) summarize known results and give closed forms for
a number of parametrized families of graphs.

Ali, G.; Laila, R.; and Ali, M. "Metric Dimension of Some Families of Graph." Math. Sci. Lett.5, 99-102, 2016.Foster-Greenwood,
B. and Uhl, C. "Metric Dimension of a Diagonal Family of Generalized Hamming
Graphs." 2 Aug 2022. https://arxiv.org/abs/2208.01519.Harary,
F. and Melter, R. A. "On the Metric Dimension of a Graph." Ars
Combin.2, 191-195, 1976.Slater, P. J. "Leaves
of Trees." Congr. Numer., No. 14, 549-559, 1975.Tillquist,
R. C.; Frongillo, R. M.; Lladser, M. .E "Getting the Lay of the
Land in Discrete Space: A Survey of Metric Dimension and its Applications."
https://arxiv.org/abs/2104.07201.Tomescu,
I. and Javid, I. "On the Metric Dimension of the Jahangir Graph." Bull.
Math. Soc. Sci. Math. Roumainie50, 371-376, 2007.