TOPICS

# Metric Dimension

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.

Graph Dimension

## Explore with Wolfram|Alpha

More things to try:

## References

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. Roumainie 50, 371-376, 2007.

## Cite this as:

Weisstein, Eric W. "Metric Dimension." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MetricDimension.html