Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and its Applications

Autor:	Tillquist, Richard C., Frongillo, Rafael M., Lladser, Manuel E.
Rok vydání:	2021
Předmět:	Mathematics - Combinatorics 05C12 05C60 05C62 05C85 05C90 68R10
Druh dokumentu:	Working Paper
Popis:	The metric dimension of a graph is the smallest number of nodes required to identify all other nodes based on shortest path distances uniquely. Applications of metric dimension include discovering the source of a spread in a network, canonically labeling graphs, and embedding symbolic data in low-dimensional Euclidean spaces. This survey gives a self-contained introduction to metric dimension and an overview of the quintessential results and applications. We discuss methods for approximating the metric dimension of general graphs, and specific bounds and asymptotic behavior for deterministic and random families of graphs. We conclude with related concepts and directions for future work. Comment: 29 pages, 10 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2104.07201 Zobrazit plný text záznamu View this record from Arxiv