Truncated Metric Dimension for Finite Graphs

Abstract

A graph $G=(V,E)$ with geodesic distance $d(\cdot ,\cdot )$ is said to be resolved by a non-empty subset $R$ of its vertices when, for all vertices $u$ and $v$, if $d(u,r)=d(v,r)$ for each $r\in R$, then $u=v$. The metric dimension of $G$ is the cardinality of its smallest resolving set. In this manuscript, we present and investigate the notions of resolvability and metric dimension when the geodesic distance is truncated with a certain threshold $k$; namely, we measure distances in $G$ using the metric $d_k(u,v):=\min \{d(u,v),k+1\}$. We denote the metric dimension of $G$ with respect to $d_k$ as ${\beta }_k(G)$. We study the behavior of this quantity with respect to $k$ as well as the diameter of $G$. We also characterize the truncated metric dimension of paths and cycles as well as graphs with extreme metric dimension, including graphs of order $n$ such that ${\beta }_k(G)=n-2$ and ${\beta }_k(G)=n-1$. We conclude with a study of various problems related to the truncated metric dimension of trees.

16 pages, 3 figures