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

2021/04/15 by Richard C. Tillquist, Rafael Frongillo, Tillquist, Richard C. +4 · 19 citations
Computer Science · Mathematics · #05C12 #05C60 #05C62 #05C85 #05C90 #68R10 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Mobile Ad Hoc Networks #Opportunistic and Delay-Tolerant Networks #math.CO #msc:05C12 #msc:05C60 #msc:05C62 #msc:05C85 #msc:05C90 #msc:68R10

paper · pdf · doi:10.48550/arxiv.2104.07201

29 pages, 10 figures

arxiv created 2021/04/15 · openalex publication_date 2021/04/15 · arxiv updated 2021/04/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• Equidistant dimension of Cartesian product graphs
• Maker-Breaker resolving game played on lexicographic products of graphs
• Optimal graph joining with applications to isomorphism detection and identification
• Reconstruction and Secrecy under Approximate Distance Queries
• Metric Dimension of Generalized Theta Graphs
• Throttling for metric dimension and its variants
• Mixed metric dimension of 2-connected graphs
• Chordless cycle filtrations for dimensionality detection in complex networks via topological data analysis
• Distance-based (and path-based) covering problems for graphs of given cyclomatic number
• On the Metric Dimension of Generalized Petersen Graphs P(n,3)
• The connectivity dimension of a graph
• Intertwining local (adjacency) metric dimension with the clique number of a graph
• On the local metric dimension of K₅-free graphs
• Metric Dimension of a Direct Product of Three Complete Graphs: The Middle Cone Family
• Multiset Metric Dimension of Binomial Random Graphs
• On the (k,ℓ)-multiset anonymity measure for social graphs
• LoRA Fine-Tuning Without GPUs: A CPU-Efficient Meta-Generation Framework for LLMs
• On the local metric dimension of K₄-free graphs
• On the weak k-metric dimension of Hamming graphs

Related

• Metric dimension for random graphs
• Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results
• Metric Dimension Parameterized by Max Leaf Number
• Graphs with the edge metric dimension smaller than the metric dimension
• The k-metric dimension of graphs: a general approach