# Truncated Metric Dimension for Finite Graphs

Richard C. Tillquist 111Corresponding author
Department of Computer Science
California State University, Chico
<EMAIL_ADDRESS>Rafael M. Frongillo
Department of Computer Science
University of Colorado, Boulder
<EMAIL_ADDRESS>Manuel E. Lladser
Department of Applied Mathematics
University of Colorado, Boulder
<EMAIL_ADDRESS>
###### 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.

##  1 Introduction

Given a simple, finite graph $G=(V,E)$, let $d(u,v)$ be the shortest path or
geodesic distance between two vertices $u,v\in V$. A non-empty subset
$R\subseteq V$ is called resolving [harary1976metric, slater1975leaves] when
for all $u,v\in V$, if $d(u,r)=d(v,r)$ for all $r\in R$, then $u=v$. The nodes
of a resolving set can be used as landmarks in a graph that allow the unique
identification and representation of all vertices based on distances. In fact,
$R$ resolves $G$ if and only if the vector of distances
$d(u|R):=(d(u,r_{1}),\dots,d(u,r_{|R|}))$, for an arbitrary but fixed order of
the elements of $R$, is distinct for each $u\in V$.

The metric dimension of $G$ [harary1976metric, slater1975leaves], denoted
$\beta(G)$, is the cardinality of a smallest possible resolving set of $G$.
Finding a minimal resolving set in an arbitrary graph is an NP-hard problem
[gary1979computers]. The state-of-the-art algorithm for finding non-trivial
resolving sets in general graphs is based on the Information Content Heuristic
(ICH) [hauptmann2012approximation] and has an approximation ratio of
$1+(1+o(1))\cdot\ln|V|$ and a time complexity of $O(|V|^{3})$. For a short
introduction to these concepts see [TilFroLla19], and for a more comprehensive
one see [tillquist2021getting].

The traditional definition of metric dimension assumes knowledge of all
pairwise distances between vertices. This assumption allows any individual
vertex $v$ of a resolving set to play a key role in distinguishing any pair of
vertices, including pairs very far from $v$. In practice, however, computing
pairwise distances between all pairs of vertices in a large network may be
costly, and the quality of pairwise distance measurements may degrade with
increasing distance. Indeed, computing the distance matrix of a dense graph
has time complexity $O(|V|^{3})$ [floyd1962algorithm], whereas for a sparse
graph the complexity is $O(|V||E|+|V|^{2}\ln|V|)$ [Joh77]. On the other hand,
various models of epidemic spread over networks assume that transmission times
across edges are random but independent and identically distributed
[pinto2012locating, spinelli2016observer]. As a consequence, transmission
times between vertices with many intermediate edges can have high variance. In
this setting, resolving sets using expected transmission time between pairs of
vertices as the metric may not be effective in identifying the source of the
infection (aka ground zero).

The above factors motivate metrics in graphs that only rely on local vertex
information in the graph. For a given integer $k\geq 0$, a natural choice for
such a metric is

$d_{k}(u,v):=\min\\{d(u,v),k+1\\}.$ (1)

Accordingly, a $k$-truncated resolving set is a non-empty set $R\subseteq V$
such that for all $u,v\in V$, if $d_{k}(u,r)=d_{k}(v,r)$ for each $r\in R$
then $u=v$. Likewise, the $k$-truncated metric dimension of $G$, which we
denote $\beta_{k}(G)$, is defined as the cardinality of a smallest
$k$-truncated resolving set.

With truncated metric dimension, elements of a resolving set are only able to
distinguish vertices up to a certain distance; in particular, computation of
the full distance metric is no longer necessary. In the context of epidemics,
by limiting the number of relevant edges on any shortest path between elements
of a resolving set and other vertices in the graph, we have better control of
the uncertainty of transmission times. Indeed, since the vertices of a graph
can be at most distance $k+1$ from the nearest element of a $k$-truncated
resolving set, these elements tend to be spread out over the space defined by
the graph.

The paper is organized as follows. After presenting formal definitions and
other preliminary information in Section 2, we examine the truncated metric
dimension of paths and cycles, two graph families for which traditional metric
dimension is easily computed, in Section 3. In Section 4 we explore graph
structures with extreme truncated metric dimension. This includes
characterizations of graphs of order $n$ with truncated metric dimension
$(n-2)$ and $(n-1)$. Finally, we focus on trees in Section 5. We define
conditions under which finding truncated metric dimension exactly is
straightforward, present a dynamic program capable of discovering minimal
resolving sets on trees when only immediate neighbors are visible, and
investigate extreme constructions for graphs in this family.

Related work. When $k=1$, the metric $d_{1}$ coincides with the so-called
adjacency distance, a notion introduced in [JanOmo12] to analyze the metric
dimension of lexicographic products. This metric is defined as

$a(u,v):=\begin{cases}0,&\text{ if $u=v$};\\\ 1,&\text{ if $u\sim v$};\\\
2,&\text{ if $u\not\sim v$}.\end{cases}$

The so-called adjacency metric dimension [JanOmo12] of a graph corresponds
therefore to its $1$-truncated metric dimension. The present paper is based on
the Ph.D. thesis by the first author [Til20], which introduced the concept of
truncated metric dimension. A review paper by all three authors
[tillquist2021getting] briefly discussed truncated metric dimension. Finally,
a more recent but independent work by other authors [GenYi21] has introduced
the same notion and obtained results which overlap with ours.

##  2 Preliminaries

To formally define truncated metric dimension, we begin by defining
$k$-truncated resolving sets.

######  Definition 2.1.

($k$-Truncated Resolving Set.) Let $G=(V,E)$ be a graph. $R\subseteq V$ is a
$k$-truncated resolving set of $G$ when, for all $u,v\in V$, if
$d_{k}(u,r)=d_{k}(v,r)$ for all $r\in R$, $u=v$.

######  Definition 2.2.

($k$-Truncated Metric Dimension.) The $k$-truncated metric dimension of a
graph $G=(V,E)$ is the size of smallest $k$-truncated resolving sets of $G$
and is denoted $\beta_{k}(G)$.

Given a graph $G=(V,E)$ and a $k$-truncated resolving set $R$ on $G$, we
define

$d_{k}(v|R):=(d_{k}(v,r))_{r\in R}.$

The $k$-neighborhood of a vertex $u$ is the set of all $v\in V$ such that
$d(u,v)\leq k$. Intuitively, truncated metric dimension restricts the view of
each vertex in a graph to its $k$-neighborhood, making all vertices beyond
this neighborhood appear identical.

While the results of this paper focus on finite, connected, simple graphs, it
is sometimes convenient to focus on matrices underlying the graph structure.
To that end, the definitions above are easily extended to apply to more
general matrices adopting the perspective of multilateration
[tillquist2019low].

######  Definition 2.3.

($k$-Truncated Resolving Set of a Matrix.) Let ${\mathbf{M}}$ be an $(n\times
m)$ matrix with real entries, and ${\mathbf{M}}_{k}$ be the matrix such that
${\mathbf{M}}_{k}(a,b):=\min\\{{\mathbf{M}}(a,b),k+1\\}$.
$R\subseteq\\{1,\dots,m\\}$ is a $k$-truncated resolving set on ${\mathbf{M}}$
if, for all distinct $u,v\in\\{1,\dots,n\\}$, there is an $r\in R$ such that
${\mathbf{M}}_{k}(u,r)\neq{\mathbf{M}}_{k}(v,r)$.

######  Definition 2.4.

($k$-Truncated Metric Dimension of a Matrix.) For an $(n\times m)$ matrix
${\mathbf{M}}$ with real entries, the $k$-truncated metric dimension of
${\mathbf{M}}$ is $\beta_{k}({\mathbf{M}}):=\beta({\mathbf{M}}_{k})$. If all
rows of ${\mathbf{M}}$ are equal, its metric dimension is defined as
$+\infty$.

Importantly, for any graph $G$ and any $k\geq 0$,
$\beta_{k}(G)=\beta_{k}({\mathbf{D}})$ where ${\mathbf{D}}$ is the distance
matrix of $G$. When $k=0$ and $G$ has $n$ vertices,
${\mathbf{D}}=\mathbf{1}-\mathbb{I}$ where $\mathbf{1}$ is the $(n\times n)$
matrix of all ones and $\mathbb{I}$ is the $(n\times n)$ identity matrix. As a
result, $\beta_{0}(G)=(n-1)$. Unless otherwise stated, we assume
$\mathbf{k>0}$.

Observe that if $\delta={\hbox{diam}}(G)$ is the diameter of $G$, then
$\beta_{\delta}(G)=\beta(G)$. The following result establishes a relationship
between traditional and truncated metric dimension.

######  Lemma 2.1.

For any graph $G=(V,E)$, $\beta_{k}(G)$ is a decreasing function of $k$,
namely, $\beta_{k+1}(G)\leq\beta_{k}(G)$ for all $k>0$. In particular, if
$\delta={\hbox{diam}}(G)$, $\beta_{k}(G)=\beta(G)$ for all $k\geq\delta$.

Proof. Let $R$ be a $k$-truncated resolving set of $G$ and suppose that $r\in
R$ distinguishes $u,v\in V$, i.e. $d_{k}(u,r)\neq d_{k}(v,r)$. In particular,
since $d_{k}(\cdot,\cdot)\leq(k+1)$, we may assume without loss of generality
that $d_{k}(u,r)<(k+1)$. Then $d_{k+1}(u,r)=d_{k}(u,r)$, and
$d_{k+1}(v,r)=d_{k}(v,r)$ or $d_{k+1}(v,r)=d_{k}(v,r)+1$. In either case,
$d_{k+1}(u,r)\neq d_{k+1}(v,r)$, which implies that $R$ is a $(k+1)$-truncated
resolving set of $G$ and $\beta_{k+1}(G)\leq\beta_{k}(G)$.

Finally, since $\delta$ is the maximum shortest path distance between two
nodes in $G$, $d(u,v)=d_{k}(u,v)$ for all $u,v\in V$ and $k\geq\delta$. Hence,
$\beta(G)=\beta_{k}(G)$. $\Box$

##  3 Paths and Cycles

Let $P_{n}$ and $C_{n}$ denote the path and cycle graphs with $n$ vertices,
respectively. In the context of traditional metric dimension, these structures
are easily understood. In fact, $\beta(G)=1$ if and only if $G$ is isomorphic
to $P_{n}$ for some $n>0$ [chartrand2000resolvability], and $\beta(C_{n})=2$
for all $n>2$ [chartrand2000cycles]. For $P_{n}$, either endpoint will serve
as a minimal resolving set, while any pair of distinct vertices $u,v\in C_{n}$
such that $d(u,v)\neq\frac{n}{2}$ resolves the vertices of a cycle.

When only truncated distance information is available, the situation is
somewhat more complex. The next result establishes a simple but non-intuitive
formula for the $k$-truncated metric dimension of paths. It extends a
characterization of minimal locating dominating sets [slater1987domination],
that is $1$-truncated resolving sets such that every vertex is adjacent to at
least one element of the set.

######  Theorem 3.1.

Let $n,k>0$ and define $m:=\lfloor\frac{n}{3k+2}\rfloor$. Then

$\beta_{k}(P_{n})=\begin{cases}1,&\text{if }n=1;\\\ 2m,&\text{if
}n\bmod(3k+2)\in\\{0,1\\}\\\ 2m+1,&\text{if
}n\bmod(3k+2)\in\\{2,\dots,k+2\\}\\\ 2m+2,&\text{if
}n\bmod(3k+2)\in\\{k+3,\dots,3k+1\\}\end{cases}$

Proof. Consider the path $P_{n}$ with vertices $v_{1},\dots,v_{n}$ and let
$R=R^{\prime}\cup R^{\prime\prime}$ where

$R^{\prime}=\\{v_{i}|i\bmod(3k+2)\in\\{k+1,2(k+1)\\},i\leq(3k+2)m\\}$

and

$R^{\prime\prime}=\begin{cases}\\{v_{n}\\},&\text{ if }n=1\\\ \\{\\},&\text{
if }n\bmod(3k+2)\in\\{0,1\\}\\\ \\{v_{n}\\},&\text{ if
}n\bmod(3k+2)\in\\{2,\dots,k+2\\}\\\
\\{v_{(3k+2)m+k+1},v_{\min(n,(3k+2)m+2(k+1))}\\},&\text{ if
}n\bmod(3k+2)\in\\{k+3,\dots,3k+1\\}\end{cases}$

We claim that $R$ is a minimal $k$-truncated resolving set of $P_{n}$.

First, we show that $R$ is a $k$-truncated resolving set. If there are two
vertices $v_{i}$ and $v_{j}$ such that $i<j$ and
$d_{k}(v_{i}|R)=d_{k}(v_{j}|R)$, then, since these vertices are on a path,
$d_{k}(v_{i}|R)$ and $d_{k}(v_{j}|R)$ are either $(k+1,\dots,k+1)$ or
$(k+1,\dots,\ell,\dots,k+1)$ where $\ell\leq k$. By construction, the only
vertex at truncated distance $(k+1)$ from all elements of $R$ is
$v_{(3k+2)m+1}$ when $n>1$ and $n\bmod(3k+2)\in\\{1,k+2\\}$. On the other
hand, if $d_{k}(v_{i}|R)=d_{k}(v_{j}|R)=(k+1,\dots,\ell,\dots,k+1)$, there is
a vertex $v_{h}\in R$ such that $i<h<j$,
$d(v_{i},v_{h})=d(v_{j},v_{h})=\ell\leq k$, and
$h\bmod(3k+2)\in\\{k+1,2(k+1)\\}$. If $h\bmod(3k+2)=(k+1)$, then
$v_{\min(n,h+k+1)}\in R$. As a result,
$d(v_{i},v_{\min(n,h+k+1)})>d(v_{j},v_{\min(n,h+k+1)})$ and
$d(v_{j},v_{\min(n,h+k+1)})<(k+1)$ so that $d_{k}(v_{i}|R)\neq
d_{k}(v_{j}|R)$. If $h\bmod(3k+2)=2(k+1)$ instead, $v_{h-(k+1)}\in R$. Then
$d(v_{j},v_{h-(k+1)})>d(v_{i},v_{h-(k+1)})$ and $d(v_{i},v_{h-(k+1)})<(k+1)$
so that $d_{k}(v_{i}|R)\neq d_{k}(v_{j}|R)$. Thus, $d_{k}(v|R)$ is unique for
all vertices $v$ in $P_{n}$ and $R$ is a $k$-truncated resolving set.

Next, we show that $R$ is of minimum size. To begin, note that $R$, and
$R^{\prime}$ more specifically, divides $P_{n}$ into consecutive subpaths or
blocks $B_{1},\dots,B_{m}$ each of size $3k+2$. In particular, letting
$w_{i}=(i-1)(3k+2)$, $v_{w_{i}+k+1},v_{w_{i}+2(k+1)}\in R^{\prime}$ resolve
the vertices of $B_{i}$ and, for all vertices $v\in B_{i}$ and $r\in
R^{\prime}\setminus\\{v_{w_{i}+k+1},v_{w_{i}+2(k+1)}\\}$, $d(v,r)>k$. When
$n\bmod(3k+2)\neq 0$, $B_{m+1}$ is the final subpath of size $q=n-(3k+2)m$.

Now, we attempted to describe a $k$-truncated resolving set $\hat{R}$ of
$P_{n}$ such that $|\hat{R}|<|R|$. Our general approach will be to show that
resolving the vertices in $B_{i}$ depends on vertices in neighboring blocks
when $|\hat{R}|<|R|$ and to notice that this leaves vertices unresolved at the
ends of the path. We proceed by cases.

Case 1: If $n=1$, $|R|=1$ and there can be no smaller resolving set.

Case 2: If $n\bmod(3k+2)\in\\{0,1\\}$, $n\geq(3k+2)$ and there must be a block
$B_{i}$ containing at most one element $v_{j}$ of $\hat{R}$. Further, $B_{i}$
must contain at least one element of $\hat{R}$, otherwise
$d_{k}(v_{w_{i}+k+1}|\hat{R})=d_{k}(v_{w_{i}+k+2}|\hat{R})=(k+1,\dots,k+1)$
and these vertices would be indistinguishable.

Note that $j\not\in\\{w_{i}+1,\dots,w_{i}+k\\}$ as this would cause
$d_{k}(v_{w_{i}+2k+1}|\hat{R})=d_{k}(v_{w_{i}+2k+2}|\hat{R})=(k+1,\dots,k+1)$.
By a symmetric argument, $j\not\in\\{w_{i}+2k+3,\dots,w_{i}+3k+2\\}$. In
addition, $j\not\in\\{w_{i}+k+2,\dots,w_{i}+2k+1\\}$ as this would cause
$d_{k}(v_{j-1}|\hat{R})=d_{k}(v_{j+1}|\hat{R})=(k+1,\dots,k+1)$. So $j$ must
be $(w_{i}+k+1)$ or $(w_{i}+2k+2)$.

If $j=(w_{i}+k+1)$, the last vertex of the previous block,
$v_{w_{i-1}+3k+2}\in B_{i-1}$, must be in $\hat{R}$. If this were not the case
or if there were no previous block,
$d_{k}(v_{w_{i}+k}|\hat{R})=d_{k}(v_{w_{i}+k+2}|\hat{R})$. Subsequently,
$v_{h}$ with $w_{i-1}+k+1\leq h\leq w_{i-1}+3k+1$ must be in $\hat{R}$ so that
$d_{k}(v_{w_{i-1}+2k+1}|\hat{R})\neq(k+1,\dots,k+1)$ and $v_{w_{i-1}+2k+1}$ is
distinguished from $v_{w_{i}+2k+2}$. Repeating this argument until $B_{1}$ is
reached, we find that at least two vertices in $B_{1}$ will be
indistinguishable unless at least three vertices in $B_{1}$ are elements of
$\hat{R}$. As a result, $|\hat{R}\cap B_{1}\cap\dots\cap B_{i}|\geq|R\cap
B_{1}\cap\dots\cap B_{i}|$. That is, up to $B_{i}$, $\hat{R}$ must be at least
as large as $R$.

Similarly, $j=(w_{i}+k+1)$ forces $v_{w_{i+1}+1}\in\hat{R}$ since
$d_{k}(v_{w_{i}+2k+2}|\hat{R})=d_{k}(v_{w_{i}+2k+3}|\hat{R})=(k+1,\dots,k+1)$
otherwise. This means $v_{h}$ where $w_{i+1}+2\leq h\leq w_{i+1}+k+2$ must be
in $\hat{R}$ so that $d_{k}(v_{w_{i}+3k+2}|\hat{R})\neq
d_{k}(v_{w_{i+1}+2}|\hat{R})$. Following this same reasoning until the last
block of the path is reached, either $B_{m}$ will include at least three
elements of $\hat{R}$ or, if $n\bmod(3k+2)=1$, $v_{n}\in\hat{R}$. Thus
$|\hat{R}\cap B_{i}\cap\dots\cap B_{m+1}|\geq|R\cap B_{i}\cap\dots\cap
B_{m+1}|$

As a result, $|\hat{R}|\geq|R|$. A symmetric argument shows the same result
when $j=w_{i}+2(k+1)$.

Case 3: If $n\bmod(3k+2)\in\\{2,\dots,k+2\\}$, there are two subcases. Either
there is a block $B_{i}$ where $1\leq i\leq m$ with at most one element of
$\hat{R}$ or $B_{m+1}$ includes no elements of $\hat{R}$. In the first
subcase, an argument similar to that in Case 2 shows $|\hat{R}|\geq|R|$.

In the second subcase, note that, if $q=k+2$,
$d_{k}(v_{n-1}|\hat{R})=d_{k}(v_{n}|\hat{R})=(k+1,\dots,k+1)$ regardless of
which vertices from $B_{m}$ are in $\hat{R}$.

On the other hand, if $q<k+2$, there must be a vertex $v_{j}\in\hat{R}$ with
$(w_{m}+2k+1+q)\leq j\leq(w_{m}+3k+2)$ so that $d_{k}(v_{n-1}|\hat{R})\neq
d_{k}(v_{n}|\hat{R})$. Consequently, there must be a vertex $v_{i}\in\hat{R}$
that distinguishes $v_{j-1}$ and $v_{j+1}$. In particular, $j-(k+1)\leq i<j$
and the minimum value of $i$ is $w_{m}+k+q$.

Applying logic similar to that followed in Case 2 and working back to $B_{1}$,
this means that there must be two vertices $v_{j^{\prime}}$ and
$v_{i^{\prime}}$ in $\hat{R}$ such that $(2k+1+q)\leq j^{\prime}\leq(3k+2)$
and $j^{\prime}-(k+1)\leq i^{\prime}<j^{\prime}$. If $j=w_{m}+2k+3$, the
smallest possible value of $i^{\prime}$ is $k+q$ and
$d_{k}(v_{1}|\hat{R})=d_{k}(v_{n}|\hat{R})=(k+1,\dots,k+1)$. If
$j>w_{m}+2k+3$, $i^{\prime}>k+q$ and
$d_{k}(v_{1}|\hat{R})=d_{k}(v_{2}|\hat{R})=(k+1,\dots,k+1)$. In either case,
there must be at least one additional vertex in $\hat{R}$ to resolve $P_{n}$
and $|\hat{R}|\geq|R|$.

Case 4: If $n\bmod(3k+2)\in\\{k+3,\dots,3k+1\\}$, there are two subcases.
Either there is a block $B_{i}$ where $1\leq i\leq m$ with at most one element
of $\hat{R}$ or $B_{m+1}$ includes at most one element of $\hat{R}$. Once
again, following the logic used in Case 2, we find that $|R|-1$ vertices are
not enough to resolve the path in the first subcase.

In the second subcase, if $q>2k+2$ and $v_{j}\in\hat{R}$ with
$j\geq(3k+2)m+2$, either
$d_{k}(v_{n-1}|\hat{R})=d_{k}(v_{n}|\hat{R})=(k+1,\dots,k+1)$ or
$d_{k}(v_{j-1}|\hat{R})=d_{k}(v_{j+1}|\hat{R})=(k+1,\dots,k+1)$.

Instead, if $q\leq 2k+2$ and $v_{j}\in\hat{R}$ with $(3k+2)m+2\leq j<n$, note
that there must be a $v_{i}\in\hat{R}$ such that $d(v_{i},v_{j})\leq k$ so
that $d_{k}(v_{j-1}|\hat{R})\neq d_{k}(v_{j+1}|\hat{R})$. In particular,
$j-(k+1)\leq i<j$. As a result, there must be a vertex $v_{h}\in\hat{R}$ with
$i-(2k+1)-1\leq h<i$ so that at most one vertex is associated with the
$k$-truncated distance vector $(k+1,\dots,k+1)$. However, unless $i-(k+1)\leq
h$, $v_{h-1}$ and $v_{h+1}$ must be distinguished by an additional vertex in
$\hat{R}$. Once again following logic similar to that used in Case 2 and
working back to $B_{1}$, we find that more than two vertices in $B_{1}$ are
required to distinguish all vertices in $P_{n}$.

If $j=n$, $i\geq w_{m}+2k+3$ and the approach in the second part of Case 3 may
be used to show that $|\hat{R}|\geq|R|$.

So there is no case in which $P_{n}$ has a $k$-truncated resolving set
$\hat{R}$ smaller than $R$. As a result, $\beta_{k}(P_{n})=|R|$ and the result
follows. $\Box$

Figure 1: Minimal $1$-truncated resolving sets of $P_{n}$ for $1\leq n\leq 20$
in red.

Graphs with $k$-truncated metric dimension $1$ are now easily characterized.

######  Corollary 3.1.

$\beta_{k}(G)=1$ if and only if $G\cong P_{n}$ for some $n\leq k+2$.

Proof. Due to Theorem 3.1, $\beta_{k}(P_{n})=1$ if and only if $n\leq k+2$. On
the other hand, due to Lemma 2.1, if $\beta_{k}(G)=1$ then $\beta(G)=1$, which
implies that $G\cong P_{n}$ [chartrand2000resolvability, Theorem 2], from
which the corollary follows. $\Box$

Thinking of cycles as paths where the endpoints are adjacent allows for a
description of $\beta_{k}(C_{n})$ in terms of $\beta_{k}(P_{n})$. The critical
observation is that minimal $k$-truncated resolving sets on different blocks
of $C_{n}$ can be made independent of one another in the sense that elements
of a $k$-truncated resolving set in one block do not affect the number of
elements required to resolve any other block.

######  Corollary 3.2.

For $n>2$ and $k>0$,

$\beta_{i}(C_{n})=\begin{cases}2,&n\leq 3k+3\\\
\beta_{k}(P_{n}),&\text{otherwise}\end{cases}$

Proof. Let $C_{n}$ be a cycle with $2<n\leq 3k+3$. Since $\beta(C_{n})=2$,
Lemma 2.1 implies that $\beta_{k}(C_{n})\geq 2$. Let $R=\\{u,v\\}$ such that
$C_{n}$ is divided into two sections $S_{1}$ and $S_{2}$ where, without loss
of generality, $0\leq|S_{1}|\leq k$ and $|S_{1}|+1\leq|S_{2}|\leq 2k+1$.
Notice, the size of $S_{1}$ implies that there is no vertex $w\in S_{1}$ such
that $d(u,w)=k+1$ or $d(v,w)=k+1$. The size of $S_{2}$ implies that there is
at most one vertex $w\in S_{2}$ such that $d(u,w)=d(v,w)=k+1$. Furthermore,
since $|S_{1}|<|S_{2}|$, there are no vertices $t,w\in C_{n}$ such that
$d(u,t)=d(u,w)$ and $d(v,t)=d(v,w)$. Thus, $R$ is a resolving set and
$\beta_{k}(C_{n})=2$ in this case.

Next, let $C_{n}=v_{1},\dots,v_{n}$ be a cycle where $n>3k+3$ and let
$m=\lfloor\frac{n}{3k+2}\rfloor$. Note that
$\beta_{k}(P_{(3k+2)m+1})=\beta_{k}(P_{(3k+2)m+1-2k})$. In particular, if
$v_{(3k+2)m+2}$ and $v_{n}$ are elements of a minimal $k$-truncated resolving
set of $C_{n}\setminus\\{v_{1},\dots,v_{(3k+2)m+1}\\}$, at most $2k$ vertices
of $\\{v_{1},\dots,v_{(3k+2)m+1}\\}$ are distinguished by this resolving set
as well. However, this does not change the number of additional vertices
required to resolve $\\{v_{1},\dots,v_{(3k+2)m+1}\\}$.

Furthermore, observe that, for any minimal $k$-truncated resolving set
$R^{\prime}$ of $\\{v_{1},\dots,v_{(3k+2)m+1}\\}$ with $n>(3k+2)m+1$, we have
$d(v_{(3k+2)m+2},r)>k$ and $d(v_{n},r)>k$ for all $r\in R^{\prime}$. If this
were not the case, at least two vertices
$u,v\in\\{v_{1},\dots,v_{(3k+2)m+1}\\}$ would have
$d_{k}(v|\hat{R})=d_{k}(u|\hat{R})$. As a result,

$\beta_{k}(C_{n})=\beta_{k}(P_{(3k+2)m+1})+\begin{cases}0,&\text{ if
}n-(3k+2)m-1=0\\\ 1,&\text{ if }n-(3k+2)m-1\in\\{1,\dots,k+1\\}\\\ 2,&\text{
if }n-(3k+2)m-1\in\\{k+2,\dots,3k+1\\}\\\ \end{cases}$

The second term in the equation above is equivalent to
$\beta_{k}(P_{n-(3k+2)m-1})$ when all vertices are forced to be within
distance $(k+1)$ of an element of a $k$-truncated resolving set. In
particular, while the first term allows a single vertex $v$ with
$d_{k}(v|\hat{R})=(k+1,\dots,k+1)$, the second term does not. But then, all
together, this is the same as the size of a $k$-truncated resolving set for
$P_{n}$ and the result follows. $\Box$

##  4 Extreme Structures

In this section we show that graph structures for which $k$-truncated metric
dimension is maximal are intuitive and align with similar results concerning
traditional metric dimension. On the contrary, structures for which
$k$-truncated metric dimension is minimal are more complex. We are able to
fully characterize graphs of order $n$ with $k$-truncated metric dimension
$(n-1)$ and $(n-2)$ and we begin to establish connections between extreme
values of $\beta_{k}$ and graph diameter.

###  4.1 Graphs with $k$-Truncated Metric Dimension $(n-1)$ and $(n-2)$

The complete graph on $n$ vertices has the largest possible metric dimension
of all such structures under the traditional definition. Indeed, when $G$ has
$n$ vertices, $\beta(G)=(n-1)$ if and only if $G\cong K_{n}$, i.e. $G$ is the
complete graph on $n$ vertices [chartrand2000resolvability]. The following
lemma and corollary show that this is also the case when distances are
truncated.

######  Lemma 4.1.

For $G=(V,E)$ connected and not complete with $n=|V|>2$, $\beta_{1}(G)<(n-1)$.

Proof. Let $G=(V,E)$ be a connected but incomplete graph with $n>2$ nodes. In
particular, there must be $u,v\in V$ such that $\\{u,v\\}\not\in E$.
Furthermore, let $w\in V$ such that $\\{v,w\\}\in E$. Consider the set
$R=V\setminus\\{u,w\\}$. Since $d_{1}(v,w)=1$ and $d_{1}(v,u)=2$, $v\in R$
distinguishes $u$ and $w$. Because all other vertices of $G$ are elements of
$R$, $R$ is a $1$-truncated resolving set on $G$ of size $(n-2)$ and
$\beta_{1}(G)<(n-1)$. $\Box$

######  Corollary 4.1.

For $n\geq 2$ and $k>0$, $\beta_{k}(G)=(n-1)$ if and only if $G\cong K_{n}$.

Proof. Suppose $G=(V,E)$ is a graph with $n\geq 2$ nodes and
$\beta_{k}(G)=(n-1)$ for some $k>0$; in particular, from Lemma 2.1,
$(n-1)\leq\beta_{1}(G)$. Furthermore, $\beta_{0}(G)=(n-1)$ for any graph, so
$\beta_{1}(G)\leq(n-1)$. Hence, $\beta_{1}(G)=(n-1)$. Finally, the
contrapositive of Lemma 4.1 implies that $G$ is complete.

Next, suppose $G$ is a complete graph. Then $\beta(G)=(n-1)$ and its diameter
is $\delta=1$. Lemma 2.1 implies that $\beta_{1}(G)=\beta(G)=(n-1)$, as
claimed. $\Box$

We now characterize under what conditions $\beta_{k}(G)=(n-2)$. The result is
nearly identical to the associated characterization under traditional metric
dimension [chartrand2000resolvability, Theorem 4]. In what follows, $G\cup H$
is the disjoint union of the graphs $G$ and $H$, and $G+H$ is the disjoint
union of the graphs with all possible edges between $G$ and $H$ added.

######  Lemma 4.2.

For $k\geq 1$, $\beta_{k}(G)=(n-2)$ when $n\geq 4$ if and only if $G$ is
$K_{s,t}$ ($s,t\geq 1$), $K_{s}+\overline{K_{t}}$ ($s\geq 1$ and $t\geq 2$),
$K_{s}+(K_{1}\cup K_{t})$ ($s,t\geq 1$), or $P_{4}$ when $k=1$.

Proof. Let $G=(V,E)$ be a graph. If ${\hbox{diam}}(G)\leq k+1$ the result
follows from Theorem 4 in [chartrand2000resolvability] and Lemma 2.1. In
particular, since the diameters of $K_{s,t}$ ($s,t\geq 1$),
$K_{s}+\overline{K_{t}}$ ($s\geq 1$ and $t\geq 2$), and $K_{s}+(K_{1}\cup
K_{t})$ ($s,t\geq 1$) are all 2, $\beta_{k}$ with $k\geq 1$ for these graphs
is $(n-2)$. In addition, if $G\cong P_{4}$ and $k=1$, we have
$\beta_{1}(P_{4})=2$ from Theorem 3.1. It is left to show that
$\beta_{k}(G)<(n-2)$ with $k\geq 1$ for all $G$ with ${\hbox{diam}}(G)>2$
except $P_{4}$.

Suppose ${\hbox{diam}}(G)>k+1$, $k\geq 1$, and $G$ is not $P_{4}$. Then there
must be $v_{1},v_{4}\in V$ with $d(v_{1},v_{4})=3$ and associated shortest
path $P=v_{1}v_{2}v_{3}v_{4}$. We claim that
$R_{1}=V\setminus\\{v_{2},v_{3},v_{4}\\}$,
$R_{2}=V\setminus\\{v_{1},v_{3},v_{4}\\}$, or
$R_{3}=V\setminus\\{v_{1},v_{2},v_{4}\\}$ must be a $k$-truncated resolving
set of $G$. To show that this is the case we need only prove that at least one
of $R_{1}$, $R_{2}$, and $R_{3}$ differentiates the vertices of $P$.

Let $v\in V\setminus P$ be adjacent to at least one vertex in $P$. Since $P$
is a shortest path between $v_{1}$ and $v_{4}$, $v$ may be adjacent to at most
3 elements of $P$ but may not be adjacent to both $v_{1}$ and $v_{4}$. We
proceed by cases.

Case 1: Suppose $\\{v,v_{1}\\}\in E$. Then $v,v_{2}\in R_{2}$ distinguish the
vertices of $P$. In particular, $v$ and $v_{2}$ define the following
representation of vertices in $P$: $v_{1}=(1,1)$, $v_{2}=(2,0)$,
$v_{3}=(d_{k}(v,v_{3}),1)$, $v_{4}=(d_{k}(v,v_{4}),2)$. If $\\{v,v_{4}\\}\in
E$ instead, $R_{3}$ distinguishes the vertices of $P$ by a symmetric argument.

Case 2: Suppose $\\{v,v_{2}\\}\in E$. Then $v,v_{3}\in R_{3}$ distinguish the
vertices of $P$. In particular, $v$ and $v_{3}$ define the following
representation of vertices in $P$: $v_{1}=(2,2)$, $v_{2}=(1,1)$,
$v_{3}=(2,0)$, $v_{4}=(d_{k}(v,v_{4}),1)$. If $\\{v,v_{3}\\}\in E$ instead,
$R_{2}$ distinguishes the vertices of $P$ by a symmetric argument.

Case 3: Suppose $v$ is adjacent to an endpoint of $P$ and its neighbor.
Without loss of generality, assume $\\{v,v_{1}\\},\\{v,v_{2}\\}\in E$. Then
$v,v_{3}\in R_{3}$ distinguish the vertices of $P$. In particular, $v$ and
$v_{3}$ define the following representation of vertices in $P$: $v_{1}=(1,2)$,
$v_{2}=(1,1)$, $v_{3}=(2,0)$, $v_{4}=(d_{k}(v,v_{4}),1)$. If
$\\{v,v_{3}\\},\\{v,v_{4}\\}\in E$ instead, $R_{2}$ distinguishes the vertices
of $P$ by a symmetric argument.

Case 4: Suppose $v$ is adjacent to an endpoint of $P$ and the vertex at
distance two from the endpoint in $P$. Assume that
$\\{v,v_{1}\\},\\{v,v_{3}\\}\in E$. Then $v,v_{1}\in R_{1}$ distinguish the
vertices of $P$. In particular, $v$ and $v_{1}$ define the following
representation of vertices in $P$: $v_{1}=(1,0)$, $v_{2}=(2,1)$,
$v_{3}=(1,2)$, $v_{4}=(2,3)$. If $\\{v,v_{2}\\},\\{v,v_{4}\\}\in E$ instead,
$v,v_{1}\in R_{1}$ still distinguish the vertices of $P$. In this case we
have: $v_{1}=(2,0)$, $v_{2}=(1,1)$, $v_{3}=(2,2)$, $v_{4}=(1,3)$.

Case 5: Suppose $\\{v,v_{2}\\},\\{v,v_{3}\\}\in E$. Then $v,v_{3}\in R_{3}$
distinguish the vertices of $P$. In particular, $v$ and $v_{3}$ define the
following representation of vertices in $P$: $v_{1}=(2,2)$, $v_{2}=(1,1)$,
$v_{3}=(1,0)$, $v_{4}=(2,1)$.

Case 6: Suppose $v$ is adjacent to an endpoint as well as $v_{2}$ and $v_{3}$.
Assume that $\\{v,v_{1}\\},\\{v,v_{2}\\},\\{v,v_{3}\\}\in E$. Then $v,v_{3}\in
R_{3}$ distinguish the vertices of $P$. In particular, $v$ and $v_{3}$ define
the following representation of vertices in $P$: $v_{1}=(1,2)$, $v_{2}=(1,1)$,
$v_{3}=(1,0)$, $v_{4}=(2,1)$. If $\\{v,v_{2}\\},\\{v,v_{3}\\},\\{v,v_{4}\\}\in
E$ instead, $R_{2}$ distinguishes the vertices of $P$ by a symmetric argument.

Thus, $R_{1}$, $R_{2}$, or $R_{3}$ must serve as a $k$-truncated resolving set
of $G$. Furthermore, $|R_{1}|=|R_{2}|=|R_{3}|=(n-3)$. Hence, we have shown
that $\beta_{k}(G)<(n-2)$ with $k\geq 1$ and for any $G$ with
${\hbox{diam}}(G)>2$ except $P_{4}$. This proves the lemma. $\Box$

###  4.2 Fixed Diameter

The relationship between traditional metric dimension and graph diameter has
been well studied. There are bounds, for example, on the order of trees,
outerplanar [beaudou2018bounding], interval, and permutation graphs
[foucaud2017identification] with respect to their metric dimension and
diameter. The following corollary generalizes a result which states that, for
a graph $G$ of order $n$ and with diameter $\delta={\hbox{diam}}(G)$,
$n\leq\delta^{\beta(G)}+\beta(G)$ [khuller1996landmarks].

######  Corollary 4.2.

Let $G=(V,E)$ and $\beta_{k}=\beta_{k}(G)$. Then
$|V|\leq(k+1)^{\beta_{k}}+\beta_{k}$.

Proof. Let $R$ be a $k$-truncated resolving set of $G=(V,E)$ and define
$\beta_{k}:=|R|$. For $v\in V\setminus R$,
$d_{k}(v|R)=(d_{k}(v,r_{1}),\dots,d_{k}(v,r_{\beta_{k}}))$, the vector of
distances from $v$ to each element of $R$, has $\beta_{k}$ dimensions each
taking a value in $\\{1,\dots,k+1\\}$. There are at most $(k+1)^{\beta_{k}}$
such vectors. For each $v\in R$, $d_{k}(v|R)$ has exactly one 0, providing
$\beta_{k}$ additional unique vectors. Since there must be at least one
distinct vector representation for every $v\in V$,
$|V|\leq(k+1)^{\beta_{k}}+\beta_{k}$. $\Box$

Next, we show a simple upper bound on $\beta_{k}(G)$ given a fixed diameter.

######  Lemma 4.3.

$\beta_{k}(G)\leq\beta_{k}(P_{\delta+1})+(n-(\delta+1))$ for any graph
$G=(V,E)$ where $n=|V|$ and $\delta={\hbox{diam}}(G)$.

Proof. Let $G=(V,E)$ be a graph with $n=|V|$ and $\delta={\hbox{diam}}(G)$,
let $P_{\delta+1}\subseteq V$ be a shortest path in $G$ of length $\delta$
(i.e. order $\delta+1$), and let $R_{P}\subseteq P_{\delta+1}$ be a
$k$-truncated resolving set of $P_{\delta+1}$. Clearly, $R=(V\setminus
P_{\delta+1})\cup R_{P}$ is an $k$-truncated resolving set of $G$. Then, since
$|R|=(n-(\delta+1))+\beta_{k}(P_{\delta+1})$,
$\beta_{k}(G)\leq\beta_{k}(P_{\delta+1})+(n-(\delta+1))$ as claimed. $\Box$

In an effort to tighten this upper bound, we define the following
construction. Let $U_{n,\delta}$ with $n\geq\delta$ be a graph consisting of a
path $P_{\delta}$ sharing a single endpoint with a complete graph
$K_{n-\delta+1}$. In particular, $U_{n,\delta}$ has $n$ vertices and diameter
$\delta$. $U_{9,5}$ with a minimal $1$-truncated resolving set is presented as
an example in Figure 2.

c Figure 2: A visualization of $U_{9,5}$ with a minimal $1$-truncated
resolving set in red.

######  Lemma 4.4.

$\beta_{k}(U_{n,\delta})=\begin{cases}n-\delta,&\text{ if }\delta\leq
2(k+1)\\\ n-\delta+\beta_{k}(P_{\delta-2k-1}),&\text{otherwise}\end{cases}.$

for $n\geq\delta$ and $\delta\geq 1$.

Proof. Let $K\subseteq U_{n,\delta}$ and $P\subseteq U_{n,\delta}$ be the
complete graph and path subgraphs of $U_{n,\delta}$ respectively and let
$\\{c\\}=K\cap P$. Since the vertices of $K\setminus P$ are indistinguishable
with respect to one another and with respect to $P$, any $k$-truncating
resolving set $R$ of $U_{n,\delta}$ must include all but one of these
vertices. To distinguish $c$ from the unchosen vertex in $K\setminus P$, $R$
must also include $u\in P$ such that $d(u,c)\leq k$. If $\delta\leq 2(k+1)$
and $d(u,c)=\min\\{k,\delta-1\\}$, $R$ is a minimal $k$-truncating resolving
set of $U_{n,\delta}$ of size $(n-\delta)$.

For $\delta>2(k+1)$, $d_{k}(r,v)=k+1$ for all $r\in R$ and for all $v$ at
distance at least $2k$ from $c$. Indeed, all vertices within distance $(k+1)$
of $R$ are resolved by $R$ and any remaining unresolved vertices belong to
$P$. As a result, the remainder of $P$ may be treated as a path independent
from $R$ which has a minimal $k$-truncated resolving set with
$\beta_{k}(P_{\delta-2k-1})$ vertices. The result follows. $\Box$

It can be shown that
$\beta_{k}(P_{\delta+1})+(n-(\delta+1))-\beta_{k}(U_{n,\delta})\in\\{0,1\\}$.
In particular, this construction achieves the bound in Lemma 4.3 under certain
circumstances.

##  5 Trees

Many problems that are NP-complete on arbitrary graphs have efficient
solutions when restricted to trees. This is true of traditional metric
dimension [harary1976metric, slater1975leaves]. Let $T=(V,E)$ be a tree and
call $v\in V$ an exterior major vertex if it has degree at least three and
there is at least one leaf $u\in V$ for which the path $v,\dots,u$ contains no
vertices, except $v$, with degree greater than two. Let $\ell(T)$ be the set
of leaves on $T$, $\sigma(T)$ be the set of exterior major vertices on $T$,
and $\Delta(v)$ be the set of leaves associated with the exterior major vertex
$v\in\sigma(T)$. Then $\beta(T)=|\ell(T)|-|\sigma(T)|$ and
$R=\bigcup_{v\in\sigma(T)}\Delta(v)\setminus\\{x\\}$ is a minimal resolving
set where $x$ is any element of $\Delta(v)$ [chartrand2000resolvability].

As the proof that $R$ is minimal relies on having access to full distance
information, the precise relationship between this construction and truncated
metric dimension on trees is unclear. However, certain aspects of this proof
along with constraints placed on paths by tree structures, suggest that there
may be an efficient means of finding minimal $k$-truncated resolving sets on
these kinds of graphs. In this section, we present some preliminary results
regarding the behavior of truncated metric dimension on trees.

###  5.1 The $\mathbb{T}_{k}$ Family of Trees

To begin, we define a class of trees for which we can find minimal
$k$-truncated resolving sets using the construction described above for
traditional metric dimension directly.

Let $\mathbb{T}_{k}$ be a family of trees defined recursively as follows. Let
the empty tree, $T=(\\{\\},\\{\\})$, be in $\mathbb{T}_{k}$. Then
$T=(V,E)\in\mathbb{T}_{k}$ if four conditions hold.

  1. 1.

$T$ is connected.

  2. 2.

There are no vertices of degree two in $V$.

  3. 3.

For all minimal non-truncated resolving sets $R$ of $T$ and for all $v\in V$,
the vector of distances $d_{k}(v|R)$ is unique or $(k+1,\dots,k+1)$ (the
vector of all $(k+1)$’s).

  4. 4.

$T^{\prime}=T\setminus\\{v|\forall u\in V\text{ distinct from
}v,d_{k}(v|R)\neq d_{k}(u|R)\\}\in\mathbb{T}_{k}$.

Condition $(3)$ may seem difficult to verify at first glance. However,
condition $(2)$ significantly restricts the set of minimal non-truncated
resolving sets. In particular, condition $(2)$ implies that every minimal non-
truncated resolving set $R$ of $T$ must have the form
$\bigcup_{v\in\sigma(T)}\Delta(v)\setminus\\{x\\}$ where $x$ is any element of
$\Delta(v)$. To see that this is the case, consider an exterior major vertex
$v$. Condition $(2)$ implies that $v$ is directly adjacent to each of its
associated leaves in $\Delta(v)$. For any $r\in R\setminus\Delta(v)$, that is
any element of a resolving set that is not one of these leaves,
$d_{k}(r|\Delta(v))$ is the same. As a result, any resolving set must include
all but one of the elements of $\Delta(v)$. Sets of the form
$\bigcup_{v\in\sigma(T)}\Delta(v)\setminus\\{x\\}$ where $x$ is any element of
$\Delta(v)$ satisfy this property and are known to be both resolving and
minimal [chartrand2000resolvability].

The definition of $\mathbb{T}_{k}$ leads directly to an algorithm for finding
minimal $k$-truncated resolving sets for any $T\in\mathbb{T}_{k}$.
Intuitively, we can find minimal $k$-truncated resolving sets of
$T\in\mathbb{T}_{k}$ by constructing a minimal non-truncated resolving set,
removing vertices that this set resolves with $k$-truncated distances, and
repeating until we are left with a tree with at most one vertex.

######  Lemma 5.1.

Let $T_{0}\in\mathbb{T}_{k}$ and $R_{0}$ be a minimal non-truncated resolving
set on $T_{0}$. Further, let the sequence of pairs
$(T_{1},R_{1}),\dots,(T_{n},R_{n})$ be generated by repeated application of
condition $(4)$ in the definition of $\mathbb{T}_{k}$. In particular,
$T_{j}=T_{j-1}\setminus\\{v|\forall u\in V\text{ distinct from
}v,d_{k}(v|R_{j-1})\neq d_{k}(u|R_{j-1})\\}$ where $R_{j-1}$ is a minimal non-
truncated resolving set of $T_{j-1}$. If $n>0$ and $|T_{n}|=1$,
$\beta_{k}(T_{0})=\sum_{j=0}^{n-1}|R_{j}|$. Otherwise,
$\beta_{k}(T_{0})=\sum_{j=0}^{n}|R_{j}|$.

Proof. First, notice that, following an argument similar to the one above,
$R_{0}$ must be of the form
$\bigcup_{v\in\sigma(T_{0})}\Delta(v)\setminus\\{x\\}$ where $x$ is any
element of $\Delta(v)$.

Next, consider $T_{0}$ with all vertices in $T_{0}\setminus T_{j}$ resolved.
Looking for a minimal non-truncated resolving set of $T_{j}$, note that
vertices from $T_{0}\setminus T_{j}$ provide no benefit, in terms of resolving
set size, over picking vertices exclusively from $T_{j}$. In particular,
suppose $\hat{R}_{j}\subseteq T_{0}$ is a minimal non-truncated resolving set
of $T_{j}$. Similar to $R_{0}$, $\hat{R}_{j}$ must include exactly one vertex
from $|\Delta(v)|-1$ of the subtrees rooted at leaves associated with each
$v\in\sigma(T_{j})$. Let $u\in R_{j}$ and $t\in\hat{R}_{j}$ be a descendant of
$u$. Since $T_{j}\in\mathbb{T}_{k}$, it must be the case that $R_{j}$ is a
$k$-truncated resolving set of every vertex $v\in T_{j}$ such that
$d_{k}(u,v)\leq k$. However, $\\{v|v\in T_{j},d_{k}(t,v)\leq
k\\}\subseteq\\{v|v\in T_{j},d_{k}(u,v)\\}$, i.e. the set of vertices in
$T_{j}$ within distance $(k+1)$ of $t$ is a subset of the set of vertices in
$T_{j}$ within distance $(k+1)$ of $u$. Hence, $t$ cannot be used to resolve
any vertices not resolved by $u$ with $k$-truncated distances and $R_{j}$ is
minimal. This shows that $\bigcup_{j=0}^{n-1}R_{j}$ is a minimal $k$-truncated
resolving set of $T_{n-1}$.

Finally, there may be a single vertex $v\in T_{0}$ such that
$d_{k}(v,r)=(k+1)$ for all $r\in\bigcup_{j=0}^{n-1}R_{j}$. In particular, if
$n>0$ and $|T_{n}|=1$, $d_{k}(v,r)=(k+1)$ where $v\in T_{n}$ for all
$r\in\bigcup_{j=0}^{n-1}R_{j}$. Since, for all other vertices $u\in
T_{0}\setminus T_{n}$, there must be at least one
$r\in\bigcup_{j=0}^{n-1}R_{j}$ such that $d_{k}(u,r)<(k+1)$, this is a unique
representation and $\bigcup_{j=0}^{n-1}R_{j}$ is a $k$-truncated resolving set
of $T_{0}$. Otherwise, $R_{n}$ is required to differentiate the vertices of
$T_{n}$. The result follows. $\Box$

In some sense, the definition of $\mathbb{T}_{k}$ enforces independence
between subsequent iterations of this process. Since $R_{0}$ has no effect on
$T_{j}$ for $j>0$, the choice of $R_{j}$ does not need to involve $R_{0}$ or
any vertex in $T_{0}\setminus T_{j}$. Without this independence property, the
interactions between elements of any resolving set can be difficult to
characterize. However, by focusing on $k=1$ and limiting the potential
influence of each vertex to its immediate neighbors, we can describe a dynamic
program guaranteed to find minimal $1$-truncated resolving sets in polynomial
time.

###  5.2 $\beta_{1}$ on Trees

Let $T=(V,E)$ be a tree with an arbitrary root and at least two vertices and
let $T_{v}$ be the subtree of $T$ rooted at $v\in V$. For all $v\in V$ let
$C(v)$ be the set of children of $v$. We call $R\subseteq V$ a locating
dominating set when $R$ is a $1$-truncated resolving set and, for each $v\in
V$, there is at least one $r\in R$ such that $d_{1}(v,r)\leq 1$. Put another
way, every $v\in V\setminus R$ must be adjacent to a different non-empty
subset of $R$. There is an existing algorithm for finding minimal locating
dominating sets on trees, though it is not obvious how this approach might be
modified to find minimal $1$-truncated resolving sets [slater1987domination].
In this section, we describe a novel dynamic programming based algorithm for
determining $\beta_{1}(T)$ exactly on trees.

For all $v\in V$, define the following functions:

  * •

$R(v)$ is the size of minimal locating dominating sets for $T_{v}$. $R_{v}$ is
one such set.

  * •

$R^{\prime}(v)$ is the size of minimal locating dominating sets $R\subseteq
T_{v}$ for $T_{v}\setminus\\{v\\}$ such that there is at least one $r\in R$
with $d_{k}(r,v)\leq k$. $R^{\prime}_{v}$ is one such set.

  * •

$R^{\prime\prime}(v)$ is the size of minimal locating dominating sets
$R\subseteq T_{v}$ for $T_{v}\setminus\\{v\\}$. $R^{\prime\prime}_{v}$ is one
such set.

  * •

$R^{\prime\prime\prime}(v)$ is the size of minimal locating dominating sets
$R\subseteq T_{v}\setminus\\{v\\}$ for $T_{v}$. $R^{\prime\prime\prime}_{v}$
is one such set.

It is easy to see that, for all $v\in\ell(T)$ except possibly the root,
$R(v)=1$, $R^{\prime}(v)=1$, and $R^{\prime\prime}(v)=0$. Note that
$R^{\prime\prime\prime}(v)$ is undefined for leaves but, as we will see
shortly, it can be defined non-recursively. We describe expressions for each
of these functions before presenting the algorithm itself.

Assume that we have $R(u)$, $R^{\prime}(u)$, $R^{\prime\prime}(u)$, and
$R^{\prime\prime\prime}(u)$ for all $u\in C(v)$ for some $v\in V$. Consider a
locating dominating set $R_{v}$ of $T_{v}$. Either $v\in R_{v}$ or $v\not\in
R_{v}$. In the first case, all children of $v$ are adjacent to at least one
element of $R_{v}$, namely $v$. To guarantee that each child is adjacent to a
different non-empty subset of $R_{v}$, there may be a single $u\in C(v)$
adjacent only to $v\in R_{v}$ while all other $w\in C(v)\setminus\\{u\\}$ must
be adjacent to at least one other vertex of $R_{v}$. Consequently,
$R_{v}=\\{v\\}\cup R^{\prime\prime}_{u}\cup(\bigcup_{w\in
C(v)\setminus\\{u\\}}R^{\prime}_{w})$ for some choice of $u\in C(v)$. Then, in
this case and taking each $u\in C(v)$ into account, $R(v)=1+\min_{u\in
C(v)}\\{R^{\prime\prime}(u)+\sum_{w\in C(v)\setminus\\{u\\}}R^{\prime}(w)\\}$
(equation 2).

If $v\not\in R_{v}$ instead, there are two additional possibilities. Either at
least one or at least two children of $v$ are included in $R_{v}$. Suppose
$u\in C(v)$ is an element of $R_{v}$. Since it is not guaranteed that $v$ is
adjacent to some other vertex in $R_{v}$, all children of $u$ must be adjacent
to at least one other element of $R_{v}$. The remaining children of $v$ must
be located and dominated without $v$. Thus, $R_{v}=\\{u\\}\cup(\bigcup_{w\in
C(u)}R^{\prime}_{w})\cup(\bigcup_{w\in C(v)\setminus\\{u\\}}R_{w})$ for some
choice of $u\in C(v)$ and $R(v)=\min_{u\in C(v)}\\{1+\sum_{w\in
C(u)}R^{\prime}(w)+\sum_{w\in C(v)\setminus\\{u\\}}R(w)\\}$ (equation 3).

Next, suppose $u,w\in C(v)$ are both in $R_{v}$. Because $v$ is the only
vertex that can possibly be adjacent to both $u$ and $w$, we follow an
argument identical to when $v\in R_{v}$ but focus on $u$ and $w$. In
particular, to guarantee that each child of $u$ is adjacent to a different
non-empty set of $R_{v}$, there may be a single $x\in C(u)$ adjacent only to
$u\in R_{v}$ while all $y\in C(u)\setminus\\{x\\}$ must be adjacent to at
least one other vertex of $R_{v}$. A symmetric argument applies to children of
$w$. The remaining children of $v$ must be located and dominated without $v$.
As a result, $R_{v}$ can be expressed as the union of the three sets

$\displaystyle R_{u}$ $\displaystyle=\\{u\\}\cup
R^{\prime\prime}_{x_{u}}\cup(\bigcup_{y\in
C(u)\setminus\\{x_{u}\\}}R^{\prime}_{y})$ $\displaystyle R_{w}$
$\displaystyle=\\{w\\}\cup R^{\prime\prime}_{x_{w}}\cup(\bigcup_{y\in
C(w)\setminus\\{x_{w}\\}}R^{\prime}_{y})$ $\displaystyle R_{z}$
$\displaystyle=\bigcup_{x\in C(v)\setminus\\{u,w\\}}R_{x}$

for some choice of the pair $u,w\in C(v)$ and for some choice of $x_{u}$ and
$x_{w}$. Thus, in this case, $R(v)$ can be described with equations 4 – 6
below and equations 2 – 6 fully describe $R(v)$.

$\displaystyle R(v)=\min\\{$ $\displaystyle 1+\min_{u\in
C(v)}\\{R^{\prime\prime}(u)+\sum_{w\in C(v)\setminus\\{u\\}}R^{\prime}(w)\\},$
(2) $\displaystyle\min_{u\in C(v)}\\{1+\sum_{w\in
C(u)}R^{\prime}(w)+\sum_{w\in C(v)\setminus\\{u\\}}R(w)\\},$ (3)
$\displaystyle\min_{u,w\in C(v)}\\{2+\min_{x\in
C(u)}\\{R^{\prime\prime}(x)+\sum_{y\in C(u)\setminus\\{x\\}}R^{\prime}(y)\\}$
(4) $\displaystyle\phantom{................}+\min_{x\in
C(w)}\\{R^{\prime\prime}(x)+\sum_{y\in C(u)\setminus\\{x\\}}R^{\prime}(y)\\}$
(5) $\displaystyle\phantom{................}+\sum_{x\in
C(v)\setminus\\{u,w\\}}R(x)\\}\\}$ (6)

$R^{\prime}(v)$ is nearly identical to $R(v)$. The only difference occurs when
$v\not\in R^{\prime}_{v}$. Since we are not concerned with ensuring that $v$
is adjacent to a different non-empty subset of $R^{\prime}_{v}$ as compared to
all other vertices, we can focus on the case when at least one child of $v$ is
in $R^{\prime}_{v}$. Suppose $u\in C(v)$ is in $R^{\prime}_{v}$. Following an
argument similar to when $v\in R_{v}$, to guarantee that each child of $u$ is
adjacent to a different non-empty subset of $R^{\prime}_{v}$, there may be a
single $w\in C(u)$ adjacent only to $u$ while all other $x\in C(u)$ must be
adjacent to at least one other vertex of $R^{\prime}_{v}$. In this case, the
remaining children of $v$ must be located and dominated without $v$. This
yields equations 8 and 9 and a full definition of $R^{\prime}(v)$ below.

$\displaystyle R^{\prime}(v)=\min\\{$ $\displaystyle 1+\min_{u\in
C(v)}\\{R^{\prime\prime}(u)+\sum_{w\in C(v)\setminus\\{u\\}}R^{\prime}(w)\\},$
(7) $\displaystyle\min_{u\in C(v)}\\{1+\min_{w\in
C(u)}\\{R^{\prime\prime}(w)+\sum_{x\in C(u)\setminus\\{w\\}}R^{\prime}(x)\\}$
(8) $\displaystyle\phantom{..............}+\sum_{w\in
C(v)\setminus\\{u\\}}R(w)\\}\\}$ (9)

For $R^{\prime\prime}(v)$, we do not require that $v$ be adjacent to any
element of $R^{\prime\prime}_{v}$. However, all children of $v$ must be both
located and dominated. So, if $v\not\in R^{\prime\prime}_{v}$, we need sets
$R_{u}$ for each $u\in C(v)$ (equation 11). Again, the case when $v\in
R^{\prime\prime}_{v}$ is identical to the corresponding cases for $R(v)$ and
$R^{\prime}(v)$ (equation 10).

$\displaystyle R^{\prime\prime}(v)=\min\\{$ $\displaystyle 1+\min_{u\in
C(v)}\\{R^{\prime\prime}(u)+\sum_{w\in C(v)\setminus\\{u\\}}R^{\prime}(w)\\},$
(10) $\displaystyle\sum_{u\in C(v)}R(u)\\}$ (11)

Finally, $R^{\prime\prime\prime}(v)$ follows directly from $R(v)$ when
$v\not\in R_{v}$ (equations 12 – 15). We note here that, when $u\in C(v)$,
$R^{\prime\prime\prime}(u)$ forces $d_{1}(v,r)=2$ for all $r\in
R^{\prime\prime\prime}_{u}$.

$\displaystyle R^{\prime\prime\prime}(v)=\min\\{$ $\displaystyle\min_{u\in
C(v)}\\{1+\sum_{w\in C(u)}R^{\prime}(w)+\sum_{w\in
C(v)\setminus\\{u\\}}R(w)\\},$ (12) $\displaystyle\min_{u,w\in
C(v)}\\{2+\min_{x\in C(u)}\\{R^{\prime\prime}(x)+\sum_{y\in
C(u)\setminus\\{x\\}}R^{\prime}(y)\\}$ (13)
$\displaystyle\phantom{................}+\min_{x\in
C(w)}\\{R^{\prime\prime}(x)+\sum_{y\in C(u)\setminus\\{x\\}}R^{\prime}(y)\\}$
(14) $\displaystyle\phantom{................}+\sum_{x\in
C(v)\setminus\\{u,w\\}}R(x)\\}\\}$ (15)

We are now ready to define an algorithm for finding minimal $1$-truncated
resolving sets on trees.

Algorithm 1 Minimal $1$-Truncated Resolving Sets on Trees

1:Input: $T=(V,E)$, a tree with $|V|>2$

2:Output: The minimum size of $1$-truncated resolving sets of $T$

3:function $\beta_{1}$($T$)

4: $S\leftarrow\\{R(v)\\}$ with any $v\in V$ as the root

5: for all $v\in V$ do

6: $S\leftarrow S\cup\\{\sum_{u\in C(v)}R^{\prime\prime\prime}(u)\\}$

7: return $\min(S)$

Intuitively, Algorithm 1 determines the size of minimal locating dominating
sets on $T$ and then considers the possibility that each $v\in V$ may be the
only vertex not adjacent to any element of a $1$-truncated resolving set. In
particular, suppose $v\in V$ is to be this vertex. Since every $u\in C(v)$
must be located and dominated but cannot be included in any $1$-truncated
resolving set in this case, we are interested in $R^{\prime\prime\prime}_{u}$
for every $u$. Then, by definition, $R=\bigcup_{u\in
C(v)}R^{\prime\prime\prime}_{u}$ locates and dominates every vertex $w\in
V\setminus\\{v\\}$ guaranteeing that $d_{1}(v,r)=2$ for all $r\in R$ as
desired. So, by taking a minimum of all these values and the size of a minimal
locating dominating set on $T$, we are sure to find $\beta_{1}(T)$. Employing
well established methods for keeping track of vertices solving the
minimizations in $R(v)$ and $R^{\prime\prime\prime}(v)$, Algorithm 1 can be
modified to return a minimal $1$-truncated resolving set of $T$.

###  5.3 Extreme Tree Constructions

We end our exploration of truncated metric dimension on trees by examining
structures in this family with extreme values of $\beta_{k}$. As with general
graphs in Section 4, determining a tree structure on $n$ vertices with maximal
$k$-truncated metric dimension is straightforward.

######  Lemma 5.2.

For any tree $T$ with $n>2$ vertices, $\beta_{k}(T)\leq\beta_{k}(S_{n})$ with
$k\geq 1$ where $S_{n}$ is the star graph on $n$ vertices.

Proof. To begin, notice that $S_{n}$ is isomorphic to $K_{1,n-1}$, the
complete bipartite graph with partitions of size 1 and $(n-1)$. By Theorem 4
in [chartrand2000resolvability], $\beta(S_{n})=(n-2)$. Since $K_{1,n-1}$ is
not a complete graph for $n>2$, Lemmas 2.1 and 4.1 imply
$(n-2)\leq\beta_{k}(S_{n})\leq\beta_{1}(S_{n})<(n-1)$ so that
$\beta_{k}(S_{n})=(n-2)$ for all $k\geq 1$.

Let $T$ be any tree with $n>2$ vertices. Since $T$ must have $(n-1)$ edges, it
cannot be isomorphic to $K_{n}$. Applying Lemmas 2.1 and 4.1 once again,
$\beta_{k}(T)\leq\beta_{1}(T)<(n-1)$ for all $k\geq 1$ and the result follows.
$\Box$

Next, we define a family of trees $\widetilde{S}_{\beta,k}$ such that
$\beta_{k}(\widetilde{S}_{\beta,k})=\beta$. Let
$R=\\{r_{1},\dots,r_{\beta}\\}$ and, for each $r_{j}\in R$, construct a path
of length $k$ with $r_{j}$ as an endpoint. Include a single extra vertex at
the end of the path associated with $r_{1}$. This vertex will have truncated
distance $k+1$ to all elements of $R$. Now, for each $r_{j}\in
R\setminus\\{r_{1}\\}$, add a path to $r_{1}$ of length $(k+1)$ if $k=1$ and
length $k$ otherwise with $r_{j}$ and $r_{1}$ as endpoints. For each vertex
$v$ on a path connecting $r_{1}$ and $r_{j}$, add a new path of length
$k-\max\\{d(v,r_{1}),d(v,r_{j})\\}$ with $v$ as an endpoint. In particular,
the other endpoint of these paths will be at distance $k$ from at least one of
$r_{1}$ and $r_{j}$. The number of vertices added for these paths is $\lfloor
k^{2}/4\rfloor$. As a result, $\widetilde{S}_{\beta,k}$ has

$\widetilde{s}(\beta,k)=1+\beta(k+1)+(\beta-1)(k-1+\lfloor\frac{k^{2}}{4}\rfloor)$

vertices. $\widetilde{S}_{3,4}$ is given as an example in Figure 3

$r_{2}$$r_{3}$$r_{1}$ Figure 3: A visualization of $\widetilde{S}_{3,4}$ with
a minimal $4$-truncated resolving set in red.

Observe that $R$ is a $k$-truncated resolving set of
$\widetilde{S}_{\beta,k}$. Indeed, since $d(r_{i},r_{j})=k$ for each distinct
pair $r_{i},r_{j}\in R$, each individual element of $R$ resolves its
associated path of length $k$ (or $k+1$ for $r_{1}$) while $r_{j}\in
R\setminus\\{r_{1}\\}$ and $r_{1}$ together resolve all vertices $v$ such that
$0<d(v,r_{1}),d(v,r_{j})\leq k$.

To see that $\beta_{k}(\widetilde{S}_{\beta,k})=\beta$, note that, for any set
of vertices $R^{\prime}$ in $\widetilde{S}_{\beta,k}$ such that
$|R^{\prime}|<\beta$, there must be at least two vertices $u$ and $v$ with
$d_{k}(u|R^{\prime})=d_{k}(v|R^{\prime})=(k+1,\dots,k+1)$. Thus,
$\beta_{k}(\widetilde{S}_{\beta,k})\geq\beta$. Furthermore, we believe, though
do not show, that $\beta_{k}(\widetilde{S}_{\beta,k})\leq\beta_{k}(T)$ for any
tree $T$ with $\widetilde{s}(\beta,k)$ vertices.

##  6 Conclusion

Truncated metric dimension restricts the ability of individual vertices to
accurately assess distances to far away points in a graph. This variation on
the traditional definition forces resolving sets to take a local perspective
and has the potential to provide more useful distance constrained resolving
sets in a number of real world scenarios.

In this work, we introduced this concept and explored connections to the
traditional definition as well as behavior on paths, cycles, and certain types
of trees. We also investigated graph constructions achieving upper and lower
bounds in different circumstances.

A variety of interesting questions remain open. For instance, can the
$k$-truncated metric dimension of arbitrary trees be determined efficiently?
Can approximations of $k$-truncated metric dimension be used to effectively
approximate traditional metric dimension through Lemma 2.1? How effective a
tool are $k$-truncated resolving sets for mitigating problems associated with
the accumulation of variance in transmission networks in different types of
applications? There are many avenues for future exploration related to these
ideas.

##  7 Acknowledgements

This research was partially funded by NSF IIS grant 1836914.

## References