TY - JOUR
T1 - Sharp bound on the truncated metric dimension of trees
AU - Bartha, Zsolt
AU - Komjáthy, Júlia
AU - Raes, Järvi
PY - 2023
Y1 - 2023
N2 - A k-truncated resolving set of a graph is a subset S⊆V of its vertex set such that the vector (dk(s,v))s∈S is distinct for each vertex v∈V where dk(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. Our result is that Tmdk(T)≥|T|⋅3/(k2+4k+3+1{k≡1(mod3)})+ck, disproving earlier conjectures by Frongillo et al. that suspected |T|/(⌊k2/4⌋+2k)+ck′ as general lower bound, where ck, ck′ are k-dependent constants. We provide a construction for trees with the largest number of vertices 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 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 the result of the above-mentioned work of Frongillo et al., where only trees without degree-two vertices were considered, except the simple case of a single path.
AB - A k-truncated resolving set of a graph is a subset S⊆V of its vertex set such that the vector (dk(s,v))s∈S is distinct for each vertex v∈V where dk(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. Our result is that Tmdk(T)≥|T|⋅3/(k2+4k+3+1{k≡1(mod3)})+ck, disproving earlier conjectures by Frongillo et al. that suspected |T|/(⌊k2/4⌋+2k)+ck′ as general lower bound, where ck, ck′ are k-dependent constants. We provide a construction for trees with the largest number of vertices 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 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 the result of the above-mentioned work of Frongillo et al., where only trees without degree-two vertices were considered, except the simple case of a single path.
KW - k-Truncated metric dimension
KW - Metric dimension
KW - Source detection
UR - http://www.scopus.com/inward/record.url?scp=85150174719&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2023.113410
DO - 10.1016/j.disc.2023.113410
M3 - Article
AN - SCOPUS:85150174719
SN - 0012-365X
VL - 346
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 8
M1 - 113410
ER -