TOPICS
Search

Metric Dimension


The metric dimension beta(G) (Tillquist et al. 2021) or dim(G) (Tomescu and Javid 2007, Ali et al. 2016) of a graph G 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 G be a finite connected graph with vertex set V. For vertices x,y in V, the graph distance d(x,y) is the length of the shortest path between x and y in G. Consider a subset of vertices W subset= V and refer to the vertices in W as "landmarks." Then W is called a resolving set if, for every pair of distinct vertices x,y in V-W, there exists a landmark w in W such that d(x,w)!=d(y,w). A resolving set of smallest possible size is called a metric basis for G, and the metric dimension of G 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.


See also

Graph Dimension

Explore with Wolfram|Alpha

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

Subject classifications