Sharp bound on the truncated metric dimension of trees

DOI10.1016/J.DISC.2023.113410arXiv2111.08813MaRDI QIDQ6041544FDOQ6041544

Zsolt Bartha, Järvi Raes, Júlia Komjáthy

Publication date: 31 May 2023

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: The threshold-$k$ metric dimension ($mathrm{Tmd}_k$) 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 $mathrm{Tmd}_k$ 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/(k^2+4k+3+mathbf1kequiv1pmod3)$, disproving earlier conjectures by Tillquist et al. in arXiv:2106.14314 that suspected $n/(lfloor{k}^2/4floor+2k)$ as main order term. We provide a construction for the largest possible trees with a given $mathrm{Tmd}_k$ 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 $mathrm{Tmd}_k$ 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.

Full work available at URL: https://arxiv.org/abs/2111.08813

zbMATH Keywords

metric dimensionsource detection\(k\)-truncated metric dimension

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Resolvability in graphs and the metric dimension of a graph
• On the Metric Dimension of Cartesian Products of Graphs
• On \(k\)-dimensional graphs and their bases
• Landmarks in graphs
• The \(k\)-metric dimension of the lexicographic product of graphs
• Computing the metric dimension of wheel related graphs
• \(k\)-metric resolvability in graphs
• Approximation complexity of metric dimension problem
• On the adjacency dimension of graphs
• Identifying codes and locating-dominating sets on paths and cycles
• The \(k\)-metric dimension of corona product graphs
• Extremal graph theory for metric dimension and diameter
• On the fractional metric dimension of graphs
• The metric dimension and metric independence of a graph
• On fractional metric dimension of graphs
• Domination and location in acyclic graphs
• The fractional metric dimension of graphs
• The metric dimension of Cayley digraphs
• On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results
• On the metric dimension of infinite graphs
• On the metric dimension and fractional metric dimension for hierarchical product of graphs
• Fringe trees, Crump-Mode-Jagers branching processes and \(m\)-ary search trees
• Metric dimension of critical Galton-Watson trees and linear preferential attachment trees
• Random Recursive Trees and Preferential Attachment Trees are Random Split Trees
• The power of adaptivity in source identification with time queries on the path
• Truncated metric dimension for finite graphs

Cited In (2)

• A tight bound on approximating arbitrary metrics by tree metrics
• A tight bound on approximating arbitrary metrics by tree metrics

This page was built for publication: Sharp bound on the truncated metric dimension of trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6041544)