Sharp bound on the truncated metric dimension of trees (Q6041544)

A \(k\)-truncated resolving set of a graph is a subset \(S\subseteq V\) of its vertex set such that the vector \((d_k(s, v))_{s\in S}\) is distinct for each vertex \(v\in V\) where \(d_k(x, y) = \min\{d(x, y), k + 1\}\) is the graph distance truncated at \(k + 1\). We think of elements of a \(k\)-truncated resolving set as sensors that can measure up to distance \(k\). The \(k\)-truncated metric dimension \((Tmdk)\) of a graph \(G\) is the minimum cardinality of a \(k\)-truncated resolving set of \(G\). We give a sharp lower bound on \(Tmdk\) for any tree \(T\) in terms of its number of vertices \(|T|\) and the measuring radius \(k\). The authors show that \(Tmd_k(T )\geq |T |\cdot 3/(k^2 +4k +3 + 1+ c_k)\) \((k\equiv 1 \pmod 3) \). This disproves an earlier conjecture by \textit{R. M. Frongillo} et al. [Discrete Appl. Math. 320, 150--169 (2022; Zbl 1520.05030)] that \(|T |/(k^2/4 +2k) + c_k^\prime\) is the general lower bound, where \(c_k\), \(c_k^\prime\) are \(k\)-dependent constants. A construction is presented for trees with the largest number of vertices with a given \(Tmdk\) value. The proof that the 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 subsets of vertices of 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. An improved lower bound is given for \(Tmdk\) of arbitrary trees that takes into account the structural properties of the trees, in particular, the number and length of simple paths of vertices of degree \(2\) terminating in vertices of degree \(1\). This bound complements the result of the above-mentioned work of Frongillo et al., where only trees with no vertex of degree \(2\) were considered, except for the simple case of a single path.