2021/11/16 by Zsolt Bartha, Júlia Komjáthy, Bartha, Zsolt +3
Computer Science · Mathematics · #05C05 #05C38 (Secondary) #05C69 (Primary) 05C35 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #math.CO #msc:05C05 #msc:05C35 #msc:05C38 #msc:05C69
paper · pdf · doi:10.48550/arxiv.2111.08813
35 pages, 4 figures
arxiv created 2021/11/16 · openalex publication_date 2021/11/16 · arxiv updated 2021/11/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The threshold-k metric dimension (Tmdk) of a graph is the minimum number of sensors -- a subset of the vertex set -- needed to uniquely identify any vertex in the graph, solely based on its distances from the sensors, when the measuring radius of a sensor is k. We give a sharp lower bound on the Tmdk of trees, depending only on the number of vertices n and the measuring radius k. This sharp lower bound grows linearly in n with leading coefficient 3/(k2+4k+3+1\k≡ 1\pmod 3\), disproving earlier conjectures by Tillquist et al. in arXiv:2106.14314 that suspected n/(\lfloor k2/4\rfloor +2k) as main order term. We provide a construction for the largest possible trees with a given Tmdk value. The proof that our optimal construction cannot be improved relies on edge-rewiring procedures of arbitrary (suboptimal) trees with arbitrary resolving sets, which reveal the structure of how small subsets of sensors measure and resolve certain areas in the tree that we call the attraction of those sensors. The notion of `attraction of sensors' might be useful in other contexts beyond trees to solve related problems. We also provide an improved lower bound on the Tmdk of arbitrary trees that takes into account the structural properties of the tree, in particular, the number and length of simple paths of degree-two vertices terminating in leaf vertices. This bound complements arXiv:2106.14314, where only trees without degree-two vertices were considered, except the simple case of a single path.