# The distance-$k$ dimension of graphs

Jesse Geneson1 and Eunjeong Yi2
San Jose State University, San Jose, CA 95192, USA1
Texas A&M University at Galveston, Galveston, TX 77553, USA2
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The metric dimension, $\dim(G)$, of a graph $G$ is a graph parameter motivated
by robot navigation that has been studied extensively. Let $G$ be a graph with
vertex set $V(G)$, and let $d(x,y)$ denote the length of a shortest $x-y$ path
in $G$. For a positive integer $k$ and for distinct $x,y\in V(G)$, let
$d_{k}(x,y)=\min\\{d(x,y),k+1\\}$ and let $R_{k}\\{x,y\\}=\\{z\in
V(G):d_{k}(x,z)\neq d_{k}(y,z)\\}$. A subset $S\subseteq V(G)$ is a _distance-
$k$ resolving set_ of $G$ if $|S\cap R_{k}\\{x,y\\}|\geq 1$ for any pair of
distinct $x,y\in V(G)$, and the _distance- $k$ dimension_, $\dim_{k}(G)$, of
$G$ is the minimum cardinality over all distance-$k$ resolving sets of $G$. In
this paper, we study the distance-$k$ dimension of graphs. We obtain some
general bounds for distance-$k$ dimension. For all $k\geq 1$, we characterize
connected graphs $G$ of order $n$ with $\dim_{k}(G)\geq n-2$. We determine
$\dim_{k}(G)$ when $G$ is a cycle or a path. We also examine the effect of
vertex or edge deletion on the distance-$k$ dimension of graphs.

Keywords: distance-$k$ resolving set, distance-$k$ dimension, metric
dimension, adjacency dimension
2010 Mathematics Subject Classification: 05C12, 05C38

##  1 Introduction

Let $G$ be a finite, simple, undirected, and connected graph with vertex set
$V(G)$ and edge set $E(G)$. The _distance_ between two vertices $x,y\in V(G)$,
denoted by $d(x,y)$, is the length of a shortest path between $x$ and $y$ in
$G$. Metric dimension, introduced by Slater [23] and by Harary and Melter
[15], is a graph parameter that has been studied extensively. For distinct
$x,y\in V(G)$, let $R\\{x,y\\}=\\{z\in V(G):d(x,z)\neq d(y,z)\\}$. A subset
$S\subseteq V(G)$ is a _resolving set_ of $G$ if $|S\cap R\\{x,y\\}|\geq 1$
for any pair of distinct vertices $x$ and $y$ in $G$. The _metric dimension_
of $G$, denoted by $\dim(G)$, is the minimum cardinality over all resolving
sets of $G$. It is $NP$-hard in general to compute $\dim(G)$ [19, 12].

Khuller et al. [19] considered robot navigation as one of the applications of
metric dimension, where a robot that moves from node to node knows its
distances to a set of landmarks, which are placed on the elements of the
resolving set. Assuming that a sensor that can detect long distance to
landmarks can be costly, the authors of [17] consider the situation where a
robot can only detect landmarks that are adjacent to it. They define the
adjacency dimension, $\textnormal{adim}(G)$, of $G$ to be the minimum number
of such landmarks that are needed for the robot to determine its position.
More generally, if the landmark detection range of a robot is $k>0$, then the
minimum number of such landmarks needed to determine the robot’s position on
the graph is called the distance-$k$ dimension (see [14]).

For a positive integer $k$ and for $x,y\in V(G)$, let
$d_{k}(x,y)=\min\\{d(x,y),k+1\\}$. For a positive integer $k$ and for distinct
$x,y\in V(G)$, let $R_{k}\\{x,y\\}=\\{z\in V(G):d_{k}(x,z)\neq d_{k}(y,z)\\}$.
A subset $S\subseteq V(G)$ is a _distance- $k$ resolving set_ of $G$ if
$|S\cap R_{k}\\{x,y\\}|\geq 1$ for any pair of distinct vertices $x$ and $y$
in $G$, and the _distance- $k$ dimension_ of $G$, denoted by $\dim_{k}(G)$, is
the minimum cardinality over all distance-$k$ resolving sets of $G$. The
distance-$k$ dimension of graphs was studied in [1], where it was also
investigated more generally for metric spaces. The complexity of the problem
was studied in [11] and [10], where it was shown that computing $\dim_{k}(G)$
is an NP-hard problem for any positive integer $k$. The graphs $G$ with
$\dim_{k}(G)=1$ were characterized in [9], which also investigated the problem
in a more general setting.

For an ordered set $S=\\{u_{1},u_{2},\ldots,u_{\beta}\\}\subseteq V(G)$ of
distinct vertices, the metric code and the distance-$k$ metric code,
respectively, of $v\in V(G)$ with respect to $S$ is the $\beta$-vector
$r_{S}(v)=(d(v,u_{1}),d(v,u_{2}),\ldots,d(v,u_{\beta}))$ and
$r_{k,S}(v)=(d_{k}(v,u_{1}),d_{k}(v,u_{2}),\ldots,d_{k}(v,u_{\beta}))$, where
$k$ is any positive integer. Note that a distance-1 resolving set and the
distance-1 dimension, respectively, of $G$ corresponds to an _adjacency
resolving set_ and the _adjacency dimension_ of $G$; notice
$\dim_{1}(G)=\textnormal{adim}(G)$. Jannesari and Omoomi [17] introduced
adjacency dimension as a tool to study the metric dimension of lexicographic
product graphs.

In this paper, we study the distance-$k$ dimension of graphs. The paper is
organized as follows. In Section 2, we obtain some general results on
distance-$k$ dimension of graphs. We prove that the maximum possible order of
a graph $G$ with $\dim_{d}(G)=k$ is
$(\lfloor\frac{2(d+1)}{3}\rfloor+1)^{k}+k\sum_{i=1}^{\lceil\frac{d+1}{3}\rceil}(2i-1)^{k-1}$.
It is easy to see that $\dim(G)\leq\dim_{k}(G)\leq\dim_{1}(G)$; we show that
$\frac{\dim_{k}(G)}{\dim(G)}$ and $\frac{\dim_{1}(G)}{\dim_{k}(G)}$ can
simultaneously be arbitrarily large with respect to $k$.

In Section 3, we prove characterization results for distance-$k$ dimension.
For all positive integers $k\geq 1$, we characterize all connected graphs $G$
of order $n\geq 4$ for which $\dim_{k}(G)$ equals $n-2$ or $n-1$. In the case
that $k=1$, this solves the problem from [14] of characterizing the graphs $G$
with $\textnormal{adim}(G)=n-2$ when $G$ is connected. In Section 4, we
examine the relationship between the distance-$k$ dimension and planarity of
graphs. In Section 5, we determine $\dim_{k}(G)$ for some classes of graphs,
including paths and cycles.

In Section 6, we examine the effect of vertex or edge deletion on distance-$k$
dimension of graphs. Let $v$ and $e$, respectively, denote a vertex and an
edge of a graph $G$. For any positive integer $k\geq 1$, we show that
$\dim_{k}(G-v)-\dim_{k}(G)$ can be arbitrarily large (also see [14] when
$k=1$); for $k\geq 2$, we show that $\dim_{k}(G)-\dim_{k}(G-v)$ can be
arbitrarily large, whereas it was shown in [14] that
$\dim_{1}(G)-\dim_{1}(G-v)\leq 1$. It was shown in [14] that
$\dim_{1}(G)-1\leq\dim_{1}(G-e)\leq\dim_{1}(G)+1$. We show that
$\dim_{2}(G-e)\leq\dim_{2}(G)+1$ and that $\dim_{k}(G-e)\leq\dim_{k}(G)+2$ for
$k\geq 3$. Moreover, in contrast to the case of distance-1 dimension, we show
that $\dim_{k}(G)-\dim_{k}(G-e)$ can be arbitrarily large for $k\geq 2$.

In this paragraph, we introduce some notation that we use in the paper. For
$x\in V(G)$ and $S\subseteq V(G)$, let $d(x,S)=\min\\{d(x,y):y\in S\\}$. The
_diameter_ , $\textnormal{diam}(G)$, of $G$ is $\max\\{d(x,y):x,y\in V(G)\\}$.
The _join_ of two graphs $H_{1}$ and $H_{2}$, denoted by $H_{1}+H_{2}$, is the
graph obtained from the disjoint union of two graphs $H_{1}$ and $H_{2}$ by
joining every vertex of $H_{1}$ with every vertex of $H_{2}$. We denote by
$P_{n}$, $C_{n}$, $K_{n}$, and $K_{a,n-a}$ respectively, the path, the cycle,
the complete graph, and the complete bipartite graph on $n$ vertices with one
part of size $a$. Suppose $f(x)$ and $g(x)$ are two functions defined for all
sufficiently large real numbers $x$. We write $f(x)=O(g(x))$ if there exist
positive constants $N$ and $C$ such that $|f(x)|\leq C|g(x)|$ for all $x>N$,
$f(x)=\Omega(g(x))$ if $g(x)=O(f(x))$, and $f(x)=\Theta(g(x))$ if
$f(x)=O(g(x))$ and $f(x)=\Omega(g(x))$.

##  2 General bounds

In this section, we obtain some general bounds for distance-$k$ dimension of
graphs. In order to state the results in this section, we define some
terminology. The _open neighborhood_ of a vertex $v\in V(G)$ is $N(v)=\\{u\in
V(G):uv\in E(G)\\}$. For distinct $u,w\in V(G)$, if
$N(u)-\\{w\\}=N(w)-\\{u\\}$, then $u$ and $w$ are called _twin vertices_ of
$G$. We begin with the following observations from [16, 17, 1, 9] which we use
in our proofs.

######  Observation 2.1.

Let $u$ and $w$ be twin vertices of a graph $G$, and let $k$ be a positive
integer. Then

  * (a)

_[16]_ $S\cap\\{u,w\\}\neq\emptyset$ for any resolving set $S$ of $G$;

  * (b)

$S_{k}\cap\\{u,w\\}\neq\emptyset$ for any distance-$k$ resolving set $S_{k}$
of $G$.

######  Observation 2.2.

_[17, 1]_ Let $G$ be a connected graph of order $n\geq 2$, and let $k$ and
$k^{\prime}$ be positive integers. Then

  * (a)

$\dim(G)\leq\dim_{k}(G)\leq\dim_{1}(G)$;

  * (b)

if $k>k^{\prime}$, then $\dim_{k}(G)\leq\dim_{k^{\prime}}(G)$.

######  Observation 2.3.

_[9]_ Let $G$ be a connected graph with $\textnormal{diam}(G)=d$, and let $k$
be a positive integer.

  * (a)

If $d\in\\{1,2\\}$, then $\dim_{k}(G)=\dim(G)$ for any positive integer $k$.

  * (b)

If $d\geq 2$, then $\dim_{k}(G)=\dim_{d-1}(G)=\dim(G)$ for any $k\geq d-1$.

In the next proof, we use a method similar to [5] to obtain a general upper
bound on $\dim_{k}(G)$ in terms of the diameter of $G$. In Section 3, we use
this result to characterize the connected graphs $G$ of order $n$ with
$\dim_{k}(G)=n-2$ for all $k\geq 2$ and $n\geq 4$.

######  Theorem 2.4.

If $G$ is a connected graph of order $n\geq 2$ and diameter $d$, then
$\dim_{k}(G)\leq n-\min\\{d,k+1\\}$ for all $k\geq 1$.

###### Proof.

Suppose that $u$ and $v$ are vertices in $G$ at distance $d$, and let
$u=v_{0},v_{1},\ldots,v_{d}=v$ be a path of order $d+1$ with endpoints $u$ and
$v$. If $d\leq k+1$, then let $S=V(G)-\left\\{v_{1},\ldots,v_{d}\right\\}$.
Note that $d_{k}(v_{0},v_{i})=i$ for each $1\leq i\leq d$, so $S$ is a
distance-$k$ resolving set for $G$.

Otherwise $d>k+1$. In this case, let
$S=V(G)-\left\\{v_{1},\ldots,v_{k+1}\right\\}$. Note that
$d_{k}(v_{0},v_{i})=i$ for each $1\leq i\leq k+1$, so $S$ is a distance-$k$
resolving set for $G$. ∎

In Section 5, we strengthen Theorem 2.4 after determining the value of
$\dim_{k}(P_{n})$. Next, we recall the following result by Hernando et al.

######  Theorem 2.5.

_[16]_ Let $G$ be a connected graph of order $n$, $\textnormal{diam}(G)=d$,
and $\dim(G)=\beta$. Then

$n\leq\left(\left\lfloor\frac{2d}{3}\right\rfloor+1\right)^{\beta}+\beta\sum_{i=1}^{\lceil\frac{d}{3}\rceil}(2i-1)^{\beta-1}.$

Since $\dim_{k}(G)=\beta$ implies $\dim(G)\leq\beta$ by Observation 2.2(a), we
have the following

######  Corollary 2.6.

For any positive integer $k$ and for any connected graph $G$ with
$\textnormal{diam}(G)=d$ and $\dim_{k}(G)=\beta$,

$|V(G)|\leq\left(\left\lfloor\frac{2d}{3}\right\rfloor+1\right)^{\beta}+\beta\sum_{i=1}^{\lceil\frac{d}{3}\rceil}(2i-1)^{\beta-1}.$

Using a method similar to the one in [16], we find a sharp upper bound on the
maximum possible order of a graph $G$ with $\dim_{j}(G)=k$.

######  Theorem 2.7.

The maximum possible order of a graph $G$ with $\dim_{j}(G)=k$ is
$(\lfloor\frac{2(j+1)}{3}\rfloor+1)^{k}+k\sum_{i=1}^{\lceil\frac{j+1}{3}\rceil}(2i-1)^{k-1}$.

###### Proof.

First we prove the upper bound. Let $G$ be a graph with $\dim_{j}(G)=k$. Let
$S$ be a distance-$j$ resolving set for $G$ and let $c\in[0,j]$ be an integer
constant that will be chosen at the end. For each $v\in S$ and integer
$i\in[0,c]$, define $N_{i}(v)=\left\\{x\in V(G):d_{j}(x,v)=i\right\\}$.

Observe that $|d_{j}(x,u)-d_{j}(y,u)|\leq 2i$ for any two vertices $x,y\in
N_{i}(v)$ and any vertex $u\in S$, so $d_{j}(x,v)=i$ and $d_{j}(x,t)$ has
$2i+1$ possible values for each $t\in S$ such that $t\neq v$. Thus
$|N_{i}(v)|\leq(2i+1)^{k-1}$.

Consider $x\in V(G)$ such that $x\not\in N_{i}(v)$ for all $i\in[0,c]$ and
$v\in S$, i.e., $d_{j}(x,v)\geq c+1$ for all $v\in S$. Since $S$ is a
distance-$j$ resolving set for $G$, there are at most $(j-c+1)^{k}$ such
vertices. Thus

$|V(G)|\leq(j-c+1)^{k}+k\sum_{i=0}^{c}(2i+1)^{k-1}$

Setting $c=\lceil\frac{j+1}{3}\rceil-1$ gives the upper bound. To see that the
upper bound is sharp, note that the construction in [16] of a graph $G$ of
maximum order with diameter $j+1$ and $\dim(G)=k$ must also have
$\dim_{j}(G)=k$ and the same order as the bound we just obtained. ∎

######  Remark 2.8.

In [14], there is a simple construction of a graph $G$ with $\dim_{1}(G)=k$ of
maximum order $k+2^{k}$. For the $j=2$ case, we also found a simple
construction of a graph $G$ with $\dim_{2}(G)=k$ of maximum order $k+3^{k}$,
which is similar to a construction in [13]. Start with $k$ copies of $K_{2}$,
each on vertices $a_{i}$ and $b_{i}$ for $i=1,\dots,k$. Let $c_{j}$ for
$j=1,\dots,3^{k}$ be labeled with a ternary string. Add an edge from $c_{j}$
to $a_{i}$ if the $i^{th}$ digit of $c_{j}$ is $0$. Add an edge from $c_{j}$
to $b_{i}$ if the $i^{th}$ digit of $c_{j}$ is $1$. Let
$S=\left\\{a_{1},\dots,a_{k}\right\\}$. Remove any $c_{j}$ with the same
distance-$2$ vector as $b_{i}$ with respect to $S$ for each $i=1,\dots,k$. The
resulting graph $G$ has order $k+3^{k}$, and $S$ is a distance-$2$ resolving
set, so $\dim_{2}(G)=k$.

It was shown in [7] that metric dimension is not a monotone parameter on
subgraph inclusion. Moreover, it was shown in [14] that, for two graphs $G$
and $H$ with $H\subset G$, $\frac{\dim(H)}{\dim(G)}$ and
$\frac{\dim_{1}(H)}{\dim_{1}(G)}$ can be arbitrarily large.

Following [14], for $m\geq 3$, let $H=K_{\frac{m(m+1)}{2}}$; let $V(H)$ be
partitioned into $V_{1},V_{2},\ldots,V_{m}$ such that
$V_{i}=\\{w_{i,1},w_{i,2},\ldots,w_{i,i}\\}$ with $|V_{i}|=i$, where
$i\in\\{1,2,\ldots,m\\}$. Let $G$ be the graph obtained from $H$ and $m$
isolated vertices $u_{1},u_{2},\ldots,u_{m}$ such that, for each
$i\in\\{1,2,\ldots,m\\}$, $u_{i}$ is joined by an edge to each vertex of
$V_{i}\cup(\cup_{j=i+1}^{m}\\{w_{j,i}\\})$. Since $\textnormal{diam}(H)=1$ and
$\textnormal{diam}(G)=2$, by Observation 2.3(a), $\dim(H)=\dim_{k}(H)$ and
$\dim(G)=\dim_{k}(G)$ for every positive integer $k$. Note that $H\subset G$,
$\dim(H)=\frac{m(m+1)}{2}-1$ by Theorem 3.1(c), and $\dim(G)\leq m$ since
$\\{u_{1},u_{2},\ldots,u_{m}\\}$ forms a resolving set of $G$. So,
$\frac{\dim_{k}(H)}{\dim_{k}(G)}=\frac{\dim(H)}{\dim(G)}\geq\frac{m^{2}+m-2}{2m}$
for every positive integer $k$, which implies the following.

######  Corollary 2.9.

For all positive integers $k$ and $N$, there exist connected graphs $G$ and
$H$ such that $H\subset G$ and $\frac{\dim_{k}(H)}{\dim_{k}(G)}>N$.

Next, in view of Observation 2.2(a), we show that
$\frac{\dim_{k}(G)}{\dim(G)}$ and $\frac{\dim_{1}(G)}{\dim_{k}(G)}$ can be
arbitrarily large with respect to $k$; thus, $\dim_{k}(G)-\dim(G)$ and
$\dim_{1}(G)-\dim_{k}(G)$ can be arbitrarily large with respect to $k$.

######  Proposition 2.10.

_[4]_ For the grid graph $G=P_{m}\times P_{n}$ ($m,n\geq 2$), $\dim(G)=2$.

######  Theorem 2.11.

_[14]_ For $m\geq 2$, let $G=P_{m}\times P_{m}$. Then
$\dim_{1}(G)=\Theta(m^{2})$; thus $\frac{\dim_{1}(G)}{\dim(G)}$ can be
arbitrarily large with respect to $m$.

######  Theorem 2.12.

For any positive integer $k>1$, let $G=P_{k^{2}}\times P_{k^{2}}$. Then
$\dim_{k}(G)=\Theta(k^{2})$, and thus $\frac{\dim_{k}(G)}{\dim(G)}$ and
$\frac{\dim_{1}(G)}{\dim_{k}(G)}$ can simultaneously be arbitrarily large with
respect to $k$.

###### Proof.

First, observe that $\dim(G)=2$ by Proposition 2.10, and
$\dim_{1}(G)=\Theta(k^{4})$ by Theorem 2.11. Next, we show that
$\dim_{k}(G)=\Theta(k^{2})$. Since any distance-$k$ resolving set of $G$ must
contain at least one vertex from every $P_{2k+1}\times P_{2k+1}$ subgraph of
$G$ except for at most one such subgraph,
$\dim_{k}(G)\geq\frac{k^{4}}{(2k+1)^{2}}-1$. On the other hand, if the grid
graph $P_{k^{2}}\times P_{k^{2}}$ is drawn in the $xy$-plane with the four
corners at $(1,1)$, $(k^{2},1)$, $(1,k^{2})$ and $(k^{2},k^{2})$ and with
horizontal/vertical edges of equal lengths, then
$[\cup_{j=0}^{k+1}\cup_{i=0}^{k+1}\\{(1+(k-1)i,1+(k-1)j)\\}]\cup[\cup_{j=0}^{k}\cup_{i=0}^{k}\\{(\lceil\frac{k}{2}\rceil+(k-1)i,\lceil\frac{k}{2}\rceil+(k-1)j)\\}]$
forms a distance-$k$ resolving set of $G$, and hence
$\dim_{k}(G)\leq(k+2)^{2}+(k+1)^{2}<2(k+2)^{2}$. So,
$\dim_{k}(G)=\Theta(k^{2})$. Therefore, $\frac{\dim_{k}(G)}{\dim(G)}$ and
$\frac{\dim_{1}(G)}{\dim_{k}(G)}$ can simultaneously be arbitrarily large with
respect to $k$. ∎

##  3 Characterizing graphs by their distance-$k$ dimension

It is known that, for any connected graph $G$ of order at least two,
$1\leq\dim(G)\leq|V(G)|-1$ (see [5]) and $1\leq\dim_{1}(G)\leq|V(G)|-1$ (see
[17]). We recall some characterization results on metric dimension and
distance-$1$ dimension, before proving characterization results about
distance-$k$ dimension.

######  Theorem 3.1.

_[5]_ Let $G$ be a connected graph of order $n\geq 2$. Then

  * (a)

$\dim(G)=1$ if and only if $G=P_{n}$;

  * (b)

for $n\geq 4$, $\dim(G)=n-2$ if and only if $G=K_{s,t}$ ($s,t\geq 1$),
$G=K_{s}+\overline{K_{t}}$ ($s\geq 1,t\geq 2$), or $G=K_{s}+(K_{1}\cup K_{t})$
($s,t\geq 1$), where $\overline{H}$ denotes the complement of a graph $H$;

  * (c)

$\dim(G)=n-1$ if and only if $G=K_{n}$.

######  Theorem 3.2.

_[17]_ Let $G$ be a connected graph of order $n\geq 2$. Then

  * (a)

$\dim_{1}(G)=1$ if and only if $G\in\\{P_{2},P_{3}\\}$;

  * (b)

$\dim_{1}(G)=n-1$ if and only if $G=K_{n}$.

More generally, the characterization of graphs $G$ with $\dim_{1}(G)=\beta$ is
provided in [14] (this includes disconnected graphs). Given any graph $G_{1}$
on $\beta$ vertices $v_{1},\dots,v_{\beta}$ and $G_{2}$ on $2^{\beta}$
vertices $\left\\{u_{b}\right\\}_{b\in\left\\{0,1\right\\}^{\beta}}$, define
the graph $B(G_{1},G_{2})$ to be obtained by connecting $v_{i}$ and $u_{b}$ if
and only if the $i^{th}$ digit of $b$ is $1$. Moreover, define
$\mathcal{B}(G_{1},G_{2})$ to be the family of induced subgraphs of
$B(G_{1},G_{2})$ that contain every vertex in $G_{1}$. Finally, define
$\mathcal{H}_{0}=\emptyset$ and, for each positive integer $\beta$, define
$\mathcal{H}_{\beta}$ to be the family of graphs obtained from taking the
union of $\mathcal{B}(G_{1},G_{2})$ over all graphs $G_{1}$ with $j$ vertices
$v_{1},\dots,v_{j}$ and $G_{2}$ with $2^{j}$ vertices
$\left\\{u_{b}\right\\}_{b\in\left\\{0,1\right\\}^{j}}$, for each $1\leq
j\leq\beta$.

######  Theorem 3.3.

_[14]_ For each $\beta\geq 1$, the set of graphs $G$ with $\dim_{1}(G)=\beta$
is $\mathcal{H}_{\beta}-\mathcal{H}_{\beta-1}$ up to isomorphism.

By the definition of $\dim_{k}(G)$, Observation 2.2(a), and Theorems 3.1 and
3.2, we have the following

######  Corollary 3.4.

Let $G$ be a connected graph of order $n\geq 2$, and let $k$ be any positive
integer. Then $1\leq\dim_{k}(G)\leq n-1$, and

  * (a)

_[9]_ $\dim_{k}(G)=1$ if and only if $G\in\cup_{i=2}^{k+2}\\{P_{i}\\}$,

  * (b)

$\dim_{k}(G)=n-1$ if and only if $G=K_{n}$.

In the next result, we characterize the connected graphs $G$ of order $n$ with
$\dim_{k}(G)=n-2$ for each $k\geq 2$. What is interesting is that these are
exactly the same connected graphs $G$ of order $n$ for which $\dim(G)=n-2$.

######  Theorem 3.5.

Let $G$ be a connected graph of order $n\geq 4$, and let $k\geq 2$. Then
$\dim_{k}(G)=n-2$ if and only if $G=K_{s,t}$ with $s,t\geq 1$,
$G=K_{s}+\overline{K_{t}}$ with $s\geq 1$ and $t\geq 2$, or
$G=K_{s}+(K_{1}\cup K_{t})$ with $s,t\geq 1$.

###### Proof.

First, note that all of the graphs $G$ in the statement of the theorem have
$\dim_{k}(G)=n-2$. This follows immediately from Observation 2.3(a) and the
paper [5], since all graphs $G$ in the statement of the theorem have diameter
$2$, and each of these graphs $G$ have $\dim(G)=n-2$ [5]. This proves the
backward implication of the biconditional.

Now we prove the forward implication. Suppose that $G$ is a connected graph of
order $n\geq 4$ with $\dim_{k}(G)=n-2$. Since $k\geq 2$, the diameter of $G$
must be $2$ by Theorem 2.4 and Corollary 3.4(b). Thus $\dim(G)=n-2$ by
Observation 2.3(a). Thus the result follows by Theorem 3.1(b). ∎

It is also interesting that this similarity between $\dim(G)$ and
$\dim_{k}(G)$ breaks at $k=1$. We just showed for $k\geq 2$ that the connected
graphs $G$ of order $n\geq 4$ with $\dim(G)=n-2$ are the same as the connected
graphs $G$ of order $n$ with $\dim_{k}(G)=n-2$. However when $k=1$, observe
that $\dim_{1}(P_{4})=2$ but $\dim(P_{4})=1$, so there exists a connected
graph $G$ of order $n=4$ with $\dim_{1}(G)=n-2$ and $\dim(G)<n-2$. In the next
result, we show that this is the only connected graph $G$ of order $n$ for
which $\dim_{1}(G)=n-2$ and $\dim(G)<n-2$. The next theorem answers an open
problem from [14] in the case that $G$ is connected.

######  Theorem 3.6.

Let $G$ be a connected graph of order $n\geq 4$. Then $\dim_{1}(G)=n-2$ if and
only if $G=K_{s,t}$ with $s,t\geq 1$, $G=K_{s}+\overline{K_{t}}$ with $s\geq
1$ and $t\geq 2$, $G=K_{s}+(K_{1}\cup K_{t})$ with $s,t\geq 1$, or $G=P_{4}$.

###### Proof.

First, note that all of the graphs $G$ in the statement of the theorem have
$\dim_{1}(G)=n-2$. For all of the graphs except for $P_{4}$, this follows
immediately from Observation 2.3(a) and the paper [5], since all graphs $G$ in
the statement of the theorem besides $P_{4}$ have diameter $2$, and each of
these graphs $G$ have $\dim(G)=n-2$ [5]. In the case of $P_{4}$, clearly
$\dim_{1}(P_{4})=2$. This proves the backward implication of the
biconditional.

Now we prove the forward implication. Suppose that $G$ is a connected graph of
order $n\geq 4$ with $\dim_{1}(G)=n-2$. Note that $G$ must have diameter at
most $3$, or else $\dim_{1}(G)\leq n-3$. To see why this is true, note that if
$G$ had two vertices $u$ and $v$ with $d(u,v)=4$, then there would exist
vertices $x,y,z$ in $G$ such that $u,x,y,z,v$ is an induced path of order $5$
in $G$. Then $V(G)-\left\\{u,y,v\right\\}$ would be a distance-$1$ resolving
set for $G$, contradicting the fact that $\dim_{1}(G)=n-2$, so $G$ has
diameter at most $3$.

For the first case, suppose that $G$ has diameter $3$, so there exist vertices
$u$ and $v$ in $G$ with $d(u,v)=3$. Since $d(u,v)=3$, there must exist
vertices $x,y\in V(G)$ such that $u,x,y,v$ form an induced path of order $4$
in $G$.

For contradiction, assume that $G$ has another vertex besides $u,v,x,y$. Let
$t$ be a vertex in $G$ that is not in the copy of $P_{4}$ such that $t$ is
adjacent to some vertex in the copy of $P_{4}$. Note that $t$ must be adjacent
to $x$ or $y$. To see why this is true, note that if $t$ was only adjacent to
one of $u$ or $v$ and neither of $x$ nor $y$, then $G$ would have diameter at
least $4$. If $t$ was adjacent to both $u$ and $v$, then $d(u,v)\leq 2$, a
contradiction. Thus, $t$ is adjacent to at most one of $u$ or $v$, and at
least one of $x$ or $y$. Without loss of generality, suppose that $t$ is not
adjacent to $v$.

Since $t$ is adjacent to $x$ or $y$, and $t$ is not adjacent to $v$, there are
several cases to consider. For the first case, suppose that $t$ is only
adjacent to a single vertex among $u,v,x,y$. This vertex must be $x$ or $y$.
Without loss of generality, let $t$ be adjacent to $x$. Then
$V(G)-\left\\{x,t,v\right\\}$ is a distance-$1$ resolving set for $G$, so
$\dim_{1}(G)\leq n-3$, a contradiction.

Now suppose that $t$ is adjacent to two vertices among $u,v,x,y$. We know $t$
is not adjacent to $v$, so either $t$ is adjacent to $u$ and $x$, $t$ is
adjacent to $u$ and $y$, or $t$ is adjacent to $x$ and $y$. If $t$ is adjacent
to $u$ and $x$, then $V(G)-\left\\{x,t,v\right\\}$ is a distance-$1$ resolving
set for $G$, so $\dim_{1}(G)\leq n-3$, a contradiction. If $t$ is adjacent to
$u$ and $y$, then $V(G)-\left\\{u,x,y\right\\}$ is a distance-$1$ resolving
set for $G$, so $\dim_{1}(G)\leq n-3$, a contradiction. If $t$ is adjacent to
$x$ and $y$, then $V(G)-\left\\{v,x,y\right\\}$ is a distance-$1$ resolving
set for $G$, so $\dim_{1}(G)\leq n-3$, a contradiction.

Now suppose that $t$ is adjacent to three vertices among $u,v,x,y$. Since $t$
is not adjacent to $v$, $t$ must be adjacent to $u$, $x$, and $y$. Then
$V(G)-\left\\{v,x,y\right\\}$ is a distance-$1$ resolving set for $G$, so
$\dim_{1}(G)\leq n-3$, a contradiction. This covers all of the possible cases,
since $t$ is not adjacent to $v$. Thus the only vertices in $G$ are $u,v,x,y$,
and these vertices form an induced path, so $G$ is $P_{4}$ in the case that
$G$ has diameter $3$.

Now we can assume that $G$ has diameter $2$, since we know that $G$ has
diameter at most $3$, and we have already considered the case when $G$ has
diameter $3$. Thus $\dim(G)=n-2$ by Observation 2.3(a) and the result follows
by Theorem 3.1(b). ∎

The last few results lead to a natural question. Note that the following
problem is hard in general, since computing $\dim_{k}(G)$ is NP-hard for any
positive integer $k$ [10, 12, 11, 19].

######  Question 3.7.

Can we characterize connected graphs $G$ of order $n\geq 4$ such that
$\dim_{k}(G)=\beta$, where $k\geq 1$ and $\beta\in\\{2,3,\ldots,n-3\\}$?

##  4 Planarity and the distance-$k$ dimension

Next, we consider the relation between $\dim_{k}(G)$ and planarity of $G$. A
graph is _planar_ if it can be drawn in a plane without any edge crossing. For
two graphs $G$ and $H$, $H$ is called a _minor_ of $G$ if $H$ can be obtained
from $G$ by vertex deletion, edge deletion, or edge contraction. We recall
some known results on metric dimension and its variations in conjunction with
planarity of a graph.

######  Theorem 4.1.

_[24]_ A graph $G$ is planar if and only if neither $K_{5}$ nor $K_{3,3}$ is a
minor of $G$.

######  Theorem 4.2.

_[19]_

  * (a)

A graph $G$ with $\dim(G)=2$ cannot have $K_{5}$ or $K_{3,3}$ as a subgraph.

  * (b)

There exists a non-planar graph $G$ with $\dim(G)=2$.

######  Theorem 4.3.

_[14]_

  * (a)

If $\dim_{1}(G)=2$, then $G$ is planar; see Figure 1(a) for graphs $G$ with
$\dim_{1}(G)=2$.

  * (b)

For each integer $\beta\geq 3$, there exists a non-planar graph $G$ with
$\dim_{1}(G)=\beta$.

Another variant of metric dimension, called connected metric dimension was
introduced in [8]. A resolving set $S$ of $G$ is called a _connected resolving
set_ of $G$ if the subgraph of $G$ induced by $S$ is connected, and the
_connected metric dimension_ , $\textnormal{cdim}(G)$, of $G$ is the minimum
cardinality over all connected resolving sets of $G$. For the characterization
of graphs $G$ with $\textnormal{cdim}(G)=2$, see [8].

######  Theorem 4.4.

_[8]_

  * (a)

If $\textnormal{cdim}(G)=2$, then $G$ is planar. However, there exists a non-
planar graph $G$ with $\dim(G)=2$ and $\textnormal{cdim}(G)>2$; see Figure
1(b).

  * (b)

For each integer $\beta\geq 3$, there exists a non-planar graph $G$ with
$\textnormal{cdim}(G)=\beta$.

(a)(b) Figure 1: (a) [14] The graphs $G$ satisfying $\dim_{1}(G)=2$, where
black vertices must be present, a solid edge must be present whenever the two
vertices incident to the solid edge are in the graph, but a dotted edge is not
necessarily present; (b) [8] A non-planar graph $G$ with $\dim(G)=2$ and
$\textnormal{cdim}(G)=3$, where black vertices form a minimum resolving set of
$G$.

Now, we consider the relation between distance-$k$ dimension and planarity of
graphs.

######  Theorem 4.5.

  * (a)

For each $k\geq 2$, there is a non-planar connected graph $G$ with
$\dim_{k}(G)=2$.

  * (b)

For each $k\geq 1$ and $\beta\geq 3$, there is a non-planar connected graph
$G$ with $\dim_{k}(G)=\beta$.

###### Proof.

For the first part, an example of a non-planar graph $G$ with $\dim_{k}(G)=2$
is given in Figure 1(b), where black vertices form a minimum distance-$k$
resolving set of $G$ for each $k\geq 2$.

For the second part, let $G$ be a graph obtained from $K_{m+2}$ ($m\geq 3$) by
subdividing exactly one edge once; then $G$ is non-planar by Theorem 4.1. It
was shown in [8] that $\textnormal{cdim}(G)=\dim(G)=m$. Since
$\textnormal{diam}(G)=2$, $\dim_{k}(G)=\dim(G)=m$ by Observation 2.3(a). ∎

##  5 The distance-$k$ dimension of some classes of graphs

In this section, we determine $\dim_{k}(G)$ for some classes of graphs. First,
we consider graphs $G$ with $\textnormal{diam}(G)\leq 2$. For two graphs
$H_{1}$ and $H_{2}$, $\textnormal{diam}(H_{1}+H_{2})\leq 2$; thus, by
Observation 2.3(a), $\dim(H_{1}+H_{2})=\dim_{k}(H_{1}+H_{2})$ for any positive
integer $k$.

######  Theorem 5.1.

_[2, 22]_ For $n\geq 3$,

$\dim(C_{n}+K_{1})=\left\\{\begin{array}[]{ll}3&\mbox{ if }n\in\\{3,6\\},\\\
\lfloor\frac{2n+2}{5}\rfloor&\mbox{ otherwise.}\end{array}\right.$

######  Theorem 5.2.

_[3]_ For $n\geq 1$,

$\dim(P_{n}+K_{1})=\left\\{\begin{array}[]{ll}1&\mbox{ if }n=1,\\\ 2&\mbox{ if
}n\in\\{2,3\\},\\\ 3&\mbox{ if }n=6,\\\ \lfloor\frac{2n+2}{5}\rfloor&\mbox{
otherwise.}\end{array}\right.$

By Observation 2.3(a) and Theorems 5.1 and 5.2, we have the following.

######  Corollary 5.3.

For any positive integer $k$ and for $n\geq 3$,

$\dim_{k}(C_{n}+K_{1})=\left\\{\begin{array}[]{ll}3&\mbox{ if
}n\in\\{3,6\\},\\\ \lfloor\frac{2n+2}{5}\rfloor&\mbox{
otherwise.}\end{array}\right.$

######  Corollary 5.4.

For any positive integer $k$ and for $n\geq 1$,

$\dim_{k}(P_{n}+K_{1})=\left\\{\begin{array}[]{ll}1&\mbox{ if }n=1,\\\
2&\mbox{ if }n\in\\{2,3\\},\\\ 3&\mbox{ if }n=6,\\\
\lfloor\frac{2n+2}{5}\rfloor&\mbox{ otherwise.}\end{array}\right.$

The metric dimension of complete multi-partite graphs was determined in [21].

######  Theorem 5.5.

_[21]_ For $m\geq 2$, let $G=K_{a_{1},a_{2},\ldots,a_{m}}$ be a complete
$m$-partite graph of order $n=\sum_{i=1}^{m}a_{i}$. Let $s$ be the number of
partite sets of $G$ consisting of exactly one element. Then

$\dim(G)=\left\\{\begin{array}[]{ll}n-m&\mbox{ if }s=0,\\\ n-m+s-1&\mbox{ if
}s\neq 0.\end{array}\right.$

As an immediate consequence of Observation 2.3(a) and Theorem 5.5, we have the
following.

######  Corollary 5.6.

For $m\geq 2$, let $G=K_{a_{1},a_{2},\ldots,a_{m}}$ be a complete $m$-partite
graph of order $n=\sum_{i=1}^{m}a_{i}$. Let $s$ be the number of partite sets
of $G$ consisting of exactly one element. Then, for any positive integer $k$,

$\dim_{k}(G)=\left\\{\begin{array}[]{ll}n-m&\mbox{ if }s=0,\\\ n-m+s-1&\mbox{
if }s\neq 0.\end{array}\right.$

Now, we recall the metric dimension of the Petersen graph.

######  Theorem 5.7.

_[18]_ For the Petersen graph $\mathcal{P}$, $\dim(\mathcal{P})=3$.

Since $\textnormal{diam}(\mathcal{P})=2$, Observation 2.3(a) and Theorem 5.7
imply the following

######  Corollary 5.8.

For the Petersen graph $\mathcal{P}$ and for any positive integer $k$,
$\dim_{k}(\mathcal{P})=3$.

Next, we determine the distance-$k$ dimension of cycles. We recall the
following results.

######  Proposition 5.9.

_[20]_ For $n\geq 3$, $\dim(C_{n})=2$.

######  Proposition 5.10.

_[17]_ For $n\geq 4$, $\dim_{1}(C_{n})=\lfloor\frac{2n+2}{5}\rfloor$.

Following [2], let $M$ be a set of at least two vertices of $C_{n}$, let
$u_{i}$ and $u_{j}$ be distinct vertices of $M$, and let $P$ and $P^{\prime}$
denote the two distinct $u_{i}-u_{j}$ paths determined by $C_{n}$. If either
$P$ or $P^{\prime}$, say $P$, contains only two vertices of $M$ (namely,
$u_{i}$ and $u_{j}$), then we refer to $u_{i}$ and $u_{j}$ as _neighboring
vertices_ of $M$ and the set of vertices of $P$ that belong to
$C_{n}-\\{u_{i},u_{j}\\}$ as the _gap_ of $M$ (determined by $u_{i}$ and
$u_{j}$). The two gaps of $M$ determined by a vertex of $M$ and its two
neighboring vertices of $M$ are called _neighboring gaps_. Note that, $M$ has
$r$ gaps if $|M|=r$, where some of the gaps may be empty.

######  Lemma 5.11.

For a positive integer $k$, let $M_{k}$ be a minimum distance-$k$ resolving
set of $C_{n}$ for $n\geq 2k+3$. Then

  * (a)

Every gap of $M_{k}$ contains at most $2k+1$ vertices. Moreover, at most one
gap of $M_{k}$ contains $2k+1$ vertices.

  * (b)

If a gap of $M_{k}$ contains at least $k+1$ vertices, then any neighboring
gaps contain at most $k$ vertices.

###### Proof.

For a positive integer $k$, let $M_{k}$ be a minimum distance-$k$ resolving
set of $C_{n}$ for $n\geq 2k+3$.

(a) If there is a gap of $M_{k}$ containing $2k+2$ consecutive vertices
$u_{j},u_{j+1},\ldots,u_{j+2k+1}$ of $C_{n}$, where $0\leq j\leq n-1$ and the
subscript is taken modulo $n$, then
$r_{k,M_{k}}(u_{j+k})=r_{k,M_{k}}(u_{j+k+1})$. If there exist distinct two
gaps $\\{u_{p},u_{p+1},\ldots,u_{p+2k}\\}$ and
$\\{u_{q},u_{q+1},\ldots,u_{q+2k}\\}$ of $M_{k}$, then
$r_{k,M_{k}}(u_{p+k})=r_{k,M_{k}}(u_{q+k})$.

(b) Suppose a gap of $M_{k}$ contains at least $k+1$ vertices, and one of its
neighboring gap contains more than $k$ vertices. Then there exist $2k+3$
consecutive vertices $u_{j},u_{j+1},\ldots,u_{j+2k+2}$ of $C_{n}$ such that
$M_{k}\cap\\{u_{j},u_{j+1},\ldots,u_{j+2k+2}\\}=\\{u_{j+k+1}\\}$ and
$r_{k,M_{k}}(u_{j+k})=r_{k,M_{k}}(u_{j+k+2})$. ∎

######  Theorem 5.12.

Let $n\geq 3$ and let $k$ be any positive integer.

  * (a)

If $n\leq 3k+3$, then $\dim_{k}(C_{n})=2$.

  * (b)

If $n\geq 3k+4$, then

$\dim_{k}(C_{n})=\left\\{\begin{array}[]{ll}\lfloor\frac{2n+3k-1}{3k+2}\rfloor&\mbox{
if }n\equiv 0,1,\ldots,k+2\pmod{(3k+2)},\\\
\lfloor\frac{2n+4k-1}{3k+2}\rfloor&\mbox{ if }n\equiv
k+3,\ldots,\lceil\frac{3k+5}{2}\rceil-1\pmod{(3k+2)},\\\
\lfloor\frac{2n+3k-1}{3k+2}\rfloor&\mbox{ if
}n\equiv\lceil\frac{3k+5}{2}\rceil,\ldots,3k+1\pmod{(3k+2)}.\end{array}\right.$

###### Proof.

Let $C_{n}$ be given by $u_{0},u_{1},\ldots,u_{n-1},u_{0}$ for $n\geq 3$, and
let $k$ be a positive integer.

(a) Let $n\leq 3k+3$. Since $\\{u_{0},u_{\alpha}\\}$, where
$\alpha=\min\\{2k+2,n-1\\}$, forms a distance-$k$ resolving set of $C_{n}$,
$\dim_{k}(C_{n})\leq 2$. By Corollary 3.4(a), $\dim_{k}(C_{n})\geq 2$. Thus,
$\dim_{k}(C_{n})=2$ for $n\leq 3k+3$.

(b) Let $n\geq 3k+4$; then $\dim_{k}(C_{n})\geq 3$. Since $k$ is a positive
integer, we must have $1\leq k\leq\lfloor\frac{n}{2}\rfloor-2$.

First, we show that $\dim_{k}(C_{n})\geq\lfloor\frac{2n+3k-1}{3k+2}\rfloor$;
moreover, we show that $\dim_{k}(C_{n})\geq\lfloor\frac{2n+4k-1}{3k+2}\rfloor$
if $n\equiv k+3,\ldots,\lceil\frac{3k+5}{2}\rceil-1\pmod{(3k+2)}$. Let $S_{k}$
be a minimum distance-$k$ resolving set of $C_{n}$. If $|S_{k}|=2\ell$ for
some positive integer $\ell$, then at most $\ell$ gaps contain more than $k$
vertices by Lemma 5.11(b), and those $\ell$ gaps contain at most $2k$ vertices
except possibly one gap containing $2k+1$ vertices by Lemma 5.11(a); thus, the
number of vertices belonging to the gaps of $S_{k}$ is at most $3k\ell+1$, and
hence $n-2\ell\leq 3k\ell+1$, which implies
$|S_{k}|=2\ell\geq\lceil\frac{2n-2}{3k+2}\rceil=\lfloor\frac{2n+3k-1}{3k+2}\rfloor$.
If $|S_{k}|=2\ell+1$ for some positive integer $\ell$, then at most $\ell$
gaps contain more than $k$ vertices by Lemma 5.11(b), and those $\ell$ gaps
contain at most $2k$ vertices except possibly one gap containing $2k+1$
vertices by Lemma 5.11(a); thus, the number of vertices belonging to the gaps
of $S_{k}$ is at most $3k\ell+k+1$, and hence $n-(2\ell+1)\leq 3k\ell+k+1$,
which implies
$|S_{k}|=2\ell+1\geq\lceil\frac{2n+k-2}{3k+2}\rceil=\lfloor\frac{2n+4k-1}{3k+2}\rfloor\geq\lfloor\frac{2n+3k-1}{3k+2}\rfloor$.

Now, suppose $n=(3k+2)x+j$, where $x\geq 1$ and $k+3\leq
j\leq\lceil\frac{3k+5}{2}\rceil-1$; notice $k\geq 2$. Then $|S_{k}|=2x+2$. To
see why $|S_{k}|\leq 2x+2$, for every path $P$ consisting of $3k+2$ vertices
on $C_{n}$, we put exactly two vertices of $P$ in $S_{k}$ including one end
vertex, say $v$, of $P$ and another vertex of $P$ at distance $2k+1$ from $v$
in $S_{k}$. Since $n\leq(3k+2)x+\lceil\frac{3k+5}{2}\rceil-1\leq(3k+2)x+3k+2$,
$|S_{k}|\leq 2x+2$. To see why $|S_{k}|\geq 2x+2$, first observe that
$|S_{k}|\geq 2x+1$ follows from the lower bounds that we proved in the last
paragraph. However if $|S_{k}|=2x+1$, then we proved that
$|S_{k}|\geq\lceil\frac{2n+k-2}{3k+2}\rceil\geq 2x+2$, giving a contradiction.
Since $|S_{k}|=2x+2$, we have $|S_{k}|=\lfloor\frac{2n+4k-1}{3k+2}\rfloor$ in
this case.

Now we show that $\dim_{k}(C_{n})\leq\lfloor\frac{2n+3k-1}{3k+2}\rfloor$ if
$n\equiv 0,1,\ldots,k+2\pmod{(3k+2)}$ or
$n\equiv\lceil\frac{3k+5}{2}\rceil,\ldots,3k+1\pmod{(3k+2)}$.

Case 1: $n=(3k+2)x+j$, where $x\geq 1$ and $0\leq j\leq 1$. Note that
$\lfloor\frac{2n+3k-1}{3k+2}\rfloor=2x$. Let
$S_{k}=\\{u_{0},u_{2k+2}\\}\cup(\cup_{i=1}^{x-1}\\{u_{(3k+2)i+1},u_{(3k+2)i+2k+2}\\})$.
Then $S_{k}$ is a distance-$k$ resolving set of $C_{n}$ with $|S_{k}|=2x$. So,
$\dim_{k}(C_{n})\leq|S_{k}|=2x=\lfloor\frac{2n+3k-1}{3k+2}\rfloor$.

Case 2: $n=(3k+2)x+j$, where $x\geq 1$ and $2\leq j\leq k+2$. Note that
$\lfloor\frac{2n+3k-1}{3k+2}\rfloor=2x+1$. Let
$S_{k}=\\{u_{0},u_{2k+2}\\}\cup(\cup_{i=1}^{x-1}\\{u_{(3k+2)i+1},u_{(3k+2)i+2k+2}\\})\cup\\{u_{(3k+2)x+1}\\}$.
Since $S_{k}$ is a distance-$k$ resolving set of $C_{n}$ with $|S_{k}|=2x+1$,
$\dim_{k}(C_{n})\leq|S_{k}|=2x+1=\lfloor\frac{2n+3k-1}{3k+2}\rfloor$.

Case 3: $n=(3k+2)x+j$, where $x\geq 1$ and $\lceil\frac{3k+5}{2}\rceil\leq
j\leq 3k+1$. Note that $\lfloor\frac{2n+3k-1}{3k+2}\rfloor=2x+2$. Let
$S_{k}=(\cup_{i=0}^{x-1}\\{u_{(3k+2)i},u_{(3k+2)i+2k+1}\\})\cup\\{u_{(3k+2)x},u_{\alpha}\\}$,
where $\alpha=\min\\{n-1,(3k+2)x+2k+1\\}$. Then $S_{k}$ is a distance-$k$
resolving set of $C_{n}$ with $|S_{k}|=2x+2$. So,
$\dim_{k}(C_{n})\leq|S_{k}|=2x+2=\lfloor\frac{2n+3k-1}{3k+2}\rfloor$. ∎

######  Remark 5.13.

Note that, for $n\geq 4$, Proposition 5.10 is an immediate corollary of
Theorem 5.12 when $k=1$.

Next, we determine the distance-$k$ dimension of paths. We recall the
following result.

######  Proposition 5.14.

_[17]_ For $n\geq 4$, $\dim_{1}(P_{n})=\lfloor\frac{2n+2}{5}\rfloor$.

Let $P_{n}$ be an $n$-path given by $u_{0},u_{1},\ldots,u_{n-1}$, where $n\geq
4$. Similar to the case for $C_{n}$, we define gaps and neighboring gaps of a
vertex subset $M$ of $P_{n}$ analogously, where $|M|\geq 2$. If
$d(u_{0},M)=x$, then the set $\\{u_{0},u_{1},\ldots,u_{x-1}\\}$ is called the
_initial gap_ of $M$; similarly, if $d(u_{n-1},M)=y$, then the set
$\\{u_{n-1},u_{n-2},\ldots,u_{n-y}\\}$ is called the _terminal gap_ of $M$.
The union of the initial gap and the terminal gap of $M$ is called the _union
gap_ of $M$. If $u_{0}\in M$ ($u_{n-1}\in M$, respectively), then the initial
gap (terminal gap, respectively) is empty. The following lemma is analogous to
Lemma 5.11, after adjusting for paths.

######  Lemma 5.15.

For a positive integer $k$, let $M_{k}$ be a minimum distance-$k$ resolving
set of $P_{n}$ for $n\geq k+3$. Then

  * (a)

Every gap of $M_{k}$ contains at most $2k+1$ vertices, the initial gap of
$M_{k}$ contains at most $k+1$ vertices, and the terminal gap of $M_{k}$
contains at most $k+1$ vertices. Moreover, at most one gap of $M_{k}$ contains
$2k+1$ vertices and the union gap of $M_{k}$ contains at most $2k+1$ vertices,
but not both.

  * (b)

If a gap of $M_{k}$ contains at least $k+1$ vertices, then any neighboring
gaps contain at most $k$ vertices. If the initial gap or the terminal gap of
$M_{k}$ contains at least one vertex, then its neighboring gap contains at
most $k$ vertices.

###### Proof.

Let $P_{n}$ be given by $u_{0},u_{1},\ldots,u_{n-1}$.

(a) If there is a gap of $M_{k}$ containing $2k+2$ consecutive vertices
$u_{j},u_{j+1},\ldots,u_{j+2k+1}$ of $P_{n}$, where $1\leq j\leq n-2k-2$, then
$r_{k,M_{k}}(u_{j+k})=r_{k,M_{k}}(u_{j+k+1})$. If the initial gap or the
terminal gap of $M_{k}$, say the former without loss of generality, contains
$k+2$ consecutive vertices $u_{0},u_{1},\ldots,u_{k+1}$, then
$r_{k,M_{k}}(u_{0})=r_{k,M_{k}}(u_{1})$. If there exist two distinct gaps
$u_{p},u_{p+1},\ldots,u_{p+2k}$ and $u_{q},u_{q+1},\ldots,u_{q+2k}$ of
$M_{k}$, then $r_{k,M_{k}}(u_{p+k})=r_{k,M_{k}}(u_{q+k})$. If there exists a
gap of $M_{k}$ containing $2k+1$ consecutive vertices, say
$u_{r},u_{r+1},\ldots,u_{r+2k}$, and the union gap of $M_{k}$ containing
$2k+1$ vertices, say
$(\cup_{i=0}^{k}\\{u_{i}\\})\cup(\cup_{j=1}^{k}\\{u_{n-j}\\})$, then
$r_{k,M_{k}}(u_{r+k})=r_{k,M_{k}}(u_{0})$.

(b) If a gap of $M_{k}$ contains at least $k+1$ vertices and one of its
neighboring gap contains more than $k$ vertices, then there exist $2k+3$
consecutive vertices $u_{j},u_{j+1},\ldots,u_{j+2k+2}$ of $P_{n}$ such that
$M_{k}\cap\\{u_{j},u_{j+1},\ldots,u_{j+2k+2}\\}=\\{u_{j+k+1}\\}$ and
$r_{k,M_{k}}(u_{j+k})=r_{k,M_{k}}(u_{j+k+2})$. If the initial gap or the
terminal gap of $M_{k}$, say the former, contains at least one vertex and its
neighboring gap contains more than $k$ vertices, then there exist $k+3$
consecutive vertices $u_{0},u_{1},\ldots,u_{k+2}$ of $P_{n}$ such that
$M_{k}\cap\\{u_{0},u_{1},\ldots,u_{k+2}\\}=\\{u_{1}\\}$ and
$r_{k,M_{k}}(u_{0})=r_{k,M_{k}}(u_{2})$. ∎

######  Theorem 5.16.

Let $n\geq 2$ and let $k$ be any positive integer.

  * (a)

If $n\leq k+2$, then $\dim_{k}(P_{n})=1$.

  * (b)

If $k+3\leq n\leq 3k+3$, then $\dim_{k}(P_{n})=2$.

  * (c)

If $n\geq 3k+4$, then

$\dim_{k}(P_{n})=\left\\{\begin{array}[]{ll}\lfloor\frac{2n+3k-1}{3k+2}\rfloor&\mbox{
if }n\equiv 0,1,\ldots,k+2\pmod{(3k+2)},\\\
\lfloor\frac{2n+4k-1}{3k+2}\rfloor&\mbox{ if }n\equiv
k+3,\ldots,\lceil\frac{3k+5}{2}\rceil-1\pmod{(3k+2)},\\\
\lfloor\frac{2n+3k-1}{3k+2}\rfloor&\mbox{ if
}n\equiv\lceil\frac{3k+5}{2}\rceil,\ldots,3k+1\pmod{(3k+2)}.\end{array}\right.$

###### Proof.

Let $n\geq 2$ and let $k$ be a positive integer.

(a) If $n\leq k+2$, then $\dim_{k}(P_{n})=1$ by Corollary 3.4(a).

(b) Suppose $k+3\leq n\leq 3k+3$. If $P_{n}$ is given by
$u_{0},u_{1},\ldots,u_{n-1}$, then $\\{u_{k},u_{\alpha}\\}$, where
$\alpha=\min\\{2k+1,n-1\\}$, forms a distance-$k$ resolving set of $P_{n}$;
thus $\dim_{k}(P_{n})\leq 2$. By Corollary 3.4(a), $\dim_{k}(P_{n})=2$.

(c) Let $n\geq 3k+4$. First, we show that
$\dim_{k}(P_{n})\leq\lfloor\frac{2n+3k-1}{3k+2}\rfloor$ if $n\equiv
0,1,\ldots,k+2\pmod{(3k+2)}$ or
$n\equiv\lceil\frac{3k+5}{2}\rceil,\ldots,3k+1\pmod{(3k+2)}$, and
$\dim_{k}(P_{n})\leq\lfloor\frac{2n+4k-1}{3k+2}\rfloor$ if $n\equiv
k+3,\ldots,\lceil\frac{3k+5}{2}\rceil-1\pmod{(3k+2)}$. By Lemmas 5.15 and
5.11, for $n\geq 3k+4$ every distance-$k$ resolving set of $P_{n}$ and
$C_{n}$, respectively, has cardinality at least three. Moreover, there exists
a minimum distance-$k$ resolving set $S$ of $C_{n}=P_{n}+e$ with a gap
containing $2k+1$ vertices $u_{j},u_{j+1}\ldots,u_{j+2k}$ in $C_{n}$, where
$0\leq j\leq n-1$ and the subscript is taken modulo $n$. If
$e=u_{j+k}u_{j+k+1}$, then $S$ forms a distance-$k$ resolving set of $P_{n}$;
thus $\dim_{k}(P_{n})\leq\dim_{k}(C_{n})$ and the desired upper bounds follow
from Theorem 5.12.

Second, we show that $\dim_{k}(P_{n})\geq\lfloor\frac{2n+3k-1}{3k+2}\rfloor$;
moreover, we show that $\dim_{k}(P_{n})\geq\lfloor\frac{2n+4k-1}{3k+2}\rfloor$
if $n\equiv k+3,\ldots,\lceil\frac{3k+5}{2}\rceil-1\pmod{(3k+2)}$. Let $S_{k}$
be a minimum distance-$k$ resolving set of $P_{n}$ such that the union gap of
$S_{k}$ contains $2k+1$ vertices. If $|S_{k}|=2\ell$ for some positive integer
$\ell$, then at most $\ell-1$ gaps contain more than $k$ vertices by Lemma
5.15(b) and those $\ell-1$ gaps contain at most $2k$ vertices by Lemma
5.15(a); thus, the number of vertices belonging to the gaps of $S_{k}$ or the
union gap of $S_{k}$ is at most $2k(\ell-1)+k\ell+(2k+1)=3k\ell+1$, and hence
$n-2\ell\leq 3k\ell+1$, which implies $|S_{k}|=2\ell\geq\dim_{k}(C_{n})$. If
$|S_{k}|=2\ell+1$ for some positive integer $\ell$, then at most $\ell-1$ gaps
contain more than $k$ vertices by Lemma 5.15(b) and those $\ell-1$ gaps
contain at most $2k$ vertices by Lemma 5.15(a); thus, the number of vertices
belonging to the gaps of $S_{k}$ or the union gap of $S_{k}$ is at most
$2k(\ell-1)+k(\ell+1)+(2k+1)=3k\ell+k+1$, and hence $n-(2\ell+1)\leq
3k\ell+k+1$, which implies $|S_{k}|=2\ell+1\geq\dim_{k}(C_{n})$. In each case,
$\dim_{k}(P_{n})\geq\dim_{k}(C_{n})$, and thus the desired lower bounds follow
from Theorem 5.12. ∎

######  Remark 5.17.

Note that, for $n\geq 4$, Proposition 5.14 is an immediate corollary of
Theorem 5.16 when $k=1$.

Next, we use Theorem 5.16 to strengthen the bound in Theorem 2.4.

######  Corollary 5.18.

If $G$ is a connected graph of order $n\geq 2$ and diameter $d\geq 1$, then
$\dim_{k}(G)\leq n-(d+1-\lfloor\frac{2(d+1)+4k-1}{3k+2}\rfloor)$ for all
$k\geq 1$.

###### Proof.

Suppose that $u$ and $v$ are vertices in $G$ at distance $d$, and let
$u=v_{0},v_{1},\ldots,v_{d}=v$ be a path of order $d+1$ with endpoints $u$ and
$v$. If $X=\left\\{v_{0},\ldots,v_{d}\right\\}$ and $H$ is the subgraph of $G$
restricted to $X$, then $H$ is a copy of $P_{d+1}$, so $H$ has a distance-$k$
resolving set $S$ of size at most $\lfloor\frac{2(d+1)+4k-1}{3k+2}\rfloor$ by
Theorem 5.16. Then $(V(G)-X)\cup S$ is a distance-$k$ resolving set for $G$,
which implies the corollary. ∎

##  6 The effect of vertex or edge deletion on the distance-$k$ dimension of
graphs

Let $v$ and $e$, respectively, denote a vertex and an edge of a connected
graph $G$ such that both $G-v$ and $G-e$ are connected graphs. First, we
consider the effect of vertex deletion on distance-$k$ dimension of graphs. We
recall the following results on the effect of vertex deletion on metric
dimension and distance-$1$ dimension.

######  Proposition 6.1.

  * (a)

_[2]_ $\dim(G)-\dim(G-v)$ can be arbitrarily large;

  * (b)

_[6]_ $\dim(G-v)-\dim(G)$ can be arbitrarily large.

######  Proposition 6.2.

_[14]_

  * (a)

For any graph $G$, $\dim_{1}(G)\leq\dim_{1}(G-v)+1$, where the bound is sharp.

  * (b)

The value of $\dim_{1}(G-v)-\dim_{1}(G)$ can be arbitrarily large, as $G$
varies (see Figure 2).

$v$$x_{1}$$y_{1}$$z_{1}$$x_{2}$$y_{2}$$z_{2}$$x_{3}$$y_{3}$$z_{3}$$x_{a}$$y_{a}$$z_{a}$
Figure 2: [14] Graphs $G$ such that
$\dim(G-v)-\dim(G)=\dim_{1}(G-v)-\dim_{1}(G)$ can be arbitrarily large, where
$a\geq 2$.

For graphs $G$ in Figure 2, note that
$\textnormal{diam}(G)=\textnormal{diam}(G-v)=2$, where $a\geq 2$. It was shown
in [14] that $\dim(G)=a+1$ and $\dim(G-v)=2a$. By Observation 2.3(a), for any
positive integer $k$, we have $\dim_{k}(G)=\dim(G)=a+1$ and
$\dim_{k}(G-v)=\dim(G-v)=2a$, which implies the following

######  Corollary 6.3.

Let $k$ be any positive integer. The value of $\dim_{k}(G-v)-\dim_{k}(G)$ can
be arbitrarily large, as $G$ varies.

In contrast to the case for distance-$1$ dimension (see Proposition 6.2(a)),
we show that $\dim_{k}(G)-\dim_{k}(G-v)$ can be arbitrarily large for $k\geq
2$.

######  Proposition 6.4.

For any positive integer $k\geq 2$, $\dim_{k}(G)-\dim_{k}(G-v)$ can be
arbitrarily large.

###### Proof.

Let $k\geq 2$ and $x\geq 1$ be integers. Let $G=C_{5(3k+2)x}+K_{1}$ with the
vertex $v$ in the $K_{1}$. Then
$\dim_{k}(G)=\lfloor\frac{10(3k+2)x+2}{5}\rfloor=2(3k+2)x=6kx+4x$ by Corollary
5.3, and $\dim_{k}(G-v)=\lfloor\frac{10(3k+2)x+3k-1}{3k+2}\rfloor=10x$ by
Theorem 5.12(b). So,
$\dim_{k}(G)-\dim_{k}(G-v)=6kx+4x-10x=6(k-1)x\rightarrow\infty$ as
$x\rightarrow\infty$ for $k\geq 2$. ∎

Next, we consider the effect of edge deletion on distance-$k$ dimension of
graphs. Throughout the section, let $d_{H,k}(v_{1},v_{2})$ denote
$d_{k}(v_{1},v_{2})$ in a graph $H$. We recall the following results on the
effect of edge deletion on metric dimension and distance-$1$ dimension.

######  Theorem 6.5.

_[6]_

  * (a)

For any graph $G$ and any edge $e\in E(G)$, $\dim(G-e)\leq\dim(G)+2$.

  * (b)

The value of $\dim(G)-\dim(G-e)$ can be arbitrarily large.

######  Theorem 6.6.

_[14]_ For any graph $G$ and any edge $e\in E(G)$,
$\dim_{1}(G)-1\leq\dim_{1}(G-e)\leq\dim_{1}(G)+1.$

The proof for Theorem 6.5(a) in [6], adjusted for the case of distance-$k$
dimension, provides the following result. We include its proof to be self-
contained.

######  Proposition 6.7.

Let $k\geq 3$ be any integer. For any graph $G$ and any edge $e\in E(G)$,
$\dim_{k}(G-e)\leq\dim_{k}(G)+2$.

###### Proof.

Let $S$ be a minimum distance-$k$ resolving set for $G$, and let $e=uw$. We
show that $S\cup\\{u,w\\}$ is a distance-$k$ resolving set for $G-e$. Let $x$
and $y$ be distinct vertices in $V(G-e)=V(G)$ such that, for some $z\in S$,
$d_{G,k}(x,z)\neq d_{G,k}(y,z)$ and $d_{G-e,k}(x,z)=d_{G-e,k}(y,z)$. We
consider two cases.

_Case 1: $d_{G,k}(x,z)=d_{G-e,k}(x,z)$ or $d_{G,k}(y,z)=d_{G-e,k}(y,z)$, but
not both._ Suppose $d_{G,k}(y,z)=d_{G-e,k}(y,z)$. Then
$d_{G,k}(y,z)=d_{G-e,k}(y,z)=d_{G-e,k}(x,z)>d_{G,k}(x,z)$, $d_{G,k}(x,z)\leq
k$, and the edge $e$ must lie on every $x-z$ geodesic in $G$. So, up to
transposing the labels $u$ and $w$, we have
$d_{G,k}(x,u)+d_{G,k}(u,w)+d_{G,k}(w,z)=d_{G,k}(x,z)$. Notice that
$d_{G,k}(x,u)=d_{G-e,k}(x,u)$ since there is an $x-u$ geodesic in $G$ that
does not use the edge $e$. Since
$d_{G,k}(x,u)+d_{G,k}(u,z)=d_{G,k}(x,z)<d_{G,k}(y,z)\leq
d_{G,k}(y,u)+d_{G,k}(u,z)$, we must have $d_{G,k}(x,u)<d_{G,k}(y,u)$. Then
$d_{G-e,k}(x,u)=d_{G,k}(x,u)<d_{G,k}(y,u)\leq d_{G-e,k}(y,u)$ and
$d_{G-e,k}(x,u)\leq k-1$.

_Case 2: $d_{G,k}(x,z)\neq d_{G-e,k}(x,z)$ and $d_{G,k}(y,z)\neq
d_{G-e,k}(y,z)$._ In this case, the edge $e$ must lie on every $x-z$ geodesic
and on every $y-z$ geodesic in $G$. Moreover, we must have either
$d_{G,k}(x,z)<d_{G,k}(y,z)\leq k$ or $d_{G,k}(y,z)<d_{G,k}(x,z)\leq k$. Notice
that if a geodesic from some vertex $a$ to another vertex $c$ traverses the
edge $e$ in the order $u,w$ (as apposed to $w,u$), then a geodesic containing
$e$ from any vertex $b$ to $c$ must also traverse $e$ in the order $u,w$.
Suppose that $u$ is traversed before $w$ by an $x-z$ geodesic and a $y-z$
geodesic (directed towards $z$) in $G$. Then an $x-u$ geodesic and a $y-u$
geodesic, neither containing the edge $e$, are obtained by removing a $u-z$
geodesic in $G$ from the $x-z$ geodesic and $y-z$ geodesic respectively. Thus,
$d_{G-e,k}(x,u)\neq d_{G-e,k}(y,u)$. ∎

######  Remark 6.8.

Note that Proposition 6.7 and its proof hold when $k=1$ or $k=2$. For
$k\in\\{1,2\\}$, we obtain the stronger result that
$\dim_{k}(G-e)\leq\dim_{k}(G)+1$. For $k=1$ this follows from Theorem 6.6. To
see why it is true for $k=2$, let $S$ be a minimum distance-$2$ resolving set
of $G$, let $e=uw$, and let $x$ and $y$ be distinct vertices in $V(G-e)=V(G)$
such that $d_{G,2}(x,z)\neq d_{G,2}(y,z)$ and $d_{G-e,2}(x,z)=d_{G-e,2}(y,z)$
for some $z\in S$; further, suppose that the edge $e$ lies on every $x-z$
geodesic in $G$ and $d_{G,2}(x,u)<d_{G,2}(x,w)$.

First, we consider Case 1. Then $0<d_{G,2}(x,z)\leq 2$; notice that $x\neq z$
since the edge $e$ lies on every $x-z$ geodesic in G. If $d_{G,2}(x,z)=1$,
then $e=uw=xz$; if $d_{G,2}(x,z)=2$, then $x=u$ or $xu\in E(G)$. In each case,
$S\cup\\{u\\}$ forms a distance-$2$ resolving set for $G-e$. Next, we consider
Case 2. Then $d_{G,2}(x,z)<d_{G,2}(y,z)\leq 2$ or
$d_{G,2}(y,z)<d_{G,2}(x,z)\leq 2$, say the former; then $e=uw=xz$ and $x$ lies
on every $y-z$ geodesic in $G$. So $S\cup\\{u\\}$ forms a distance-$2$
resolving set for $G-e$. Therefore, $\dim_{2}(G-e)\leq\dim_{2}(G)+1$. For
graphs $G$ satisfying $\dim_{2}(G-e)=\dim_{2}(G)+1$, see Figure 3, where
$a,b,c\geq 2$; one can easily check that
$R=(\cup_{i=1}^{a-1}\\{x_{i}\\})\cup(\cup_{i=1}^{b-1}\\{y_{i}\\})\cup(\cup_{i=1}^{c-1}\\{z_{i}\\})$
forms a minimum distance-$2$ resolving set of $G-e$ with $|R|=a+b+c-3$ and
that $R^{\prime}=R-\\{z_{1}\\}$ forms a minimum distance-$2$ resolving set for
$G$ with $|R^{\prime}|=a+b+c-4$.

######  Remark 6.9.

The bound in Proposition 6.7 is sharp. For any integer $k\geq 3$, let $G$ be
the graph in Figure 3 and let $e=x_{1}z_{1}$. Let
$L_{1}=\cup_{i=1}^{a}\\{x_{i}\\}$, $L_{2}=\cup_{i=1}^{b}\\{y_{i}\\}$ and
$L_{3}=\cup_{i=1}^{c}\\{z_{i}\\}$, where $a,c\geq 3$ and $b\geq 2$.

First, we show that $\dim_{k}(G-e)=a+b+c-3$. Note that any two vertices in
$L_{i}$ are twin vertices in $G-e$, where $i\in\\{1,2,3\\}$. So, for any
distance-$k$ resolving set $S$ of $G-e$, we have $|S\cap L_{1}|\geq a-1$,
$|S\cap L_{2}|\geq b-1$, and $|S\cap L_{3}|\geq c-1$ by Observation 2.1(b);
thus, $\dim_{k}(G-e)\geq a+b+c-3$. On the other hand, $(L_{1}\cup L_{2}\cup
L_{3})-\\{x_{1},y_{1},z_{1}\\}$ forms a distance-$k$ resolving set of $G-e$,
and hence $\dim_{k}(G-e)\leq a+b+c-3$. Thus, $\dim_{k}(G-e)=a+b+c-3$.

Second, we show that $\dim_{k}(G)=a+b+c-5$. For any distance-$k$ resolving set
$S^{\prime}$ of $G$, we have $|S^{\prime}\cap(L_{1}-\\{x_{1}\\})|\geq a-2$,
$|S^{\prime}\cap L_{2}|\geq b-1$, and $|S^{\prime}\cap(L_{3}-\\{z_{1}\\})|\geq
c-2$ by Observation 2.1(b); thus, $\dim_{k}(G)\geq a+b+c-5$. Since $(L_{1}\cup
L_{2}\cup L_{3})-\\{x_{1},x_{2},y_{1},z_{1},z_{2}\\}$ forms a distance-$k$
resolving set of $G$, $\dim_{k}(G)\leq a+b+c-5$. So, $\dim_{k}(G)=a+b+c-5$.

Therefore, $\dim_{k}(G-e)=\dim_{k}(G)+2$ for $k\geq 3$.

$x_{a}$$x_{4}$$x_{3}$$x_{2}$$x_{1}$$y_{b}$$y_{2}$$y_{1}$$z_{c}$$z_{3}$$z_{2}$$z_{1}$$e$
Figure 3: Graphs $G$ with $\dim_{2}(G-e)=\dim_{2}(G)+1$ and
$\dim_{k}(G-e)=\dim_{k}(G)+2$ for $k\geq 3$.

In contrast to Theorem 6.6, we show that $\dim_{k}(G)-\dim_{k}(G-e)$ can be
arbitrarily large for any integer $k\geq 2$.

######  Theorem 6.10.

For any integer $k\geq 2$, the value of $\dim_{k}(G)-\dim_{k}(G-e)$ can be
arbitrarily large.

###### Proof.

Let $G$ be the graph in Figure 4. For each $i\in\\{1,2,\ldots,a\\}$,
$N_{G}(x_{i})=N_{G}(y_{i})=\\{z_{i},z^{\prime}_{i}\\}=N_{G-e}(x_{i})=N_{G-e}(y_{i})$.
Let $k\geq 2$ and $a\geq 2$ be any integers. Let $S$ be any minimum
distance-$k$ resolving set for $G-e$, and let $S^{\prime}$ be any distance-$k$
resolving set for $G$. By Observation 2.1(b),
$S\cap\\{x_{i},y_{i}\\}\neq\emptyset$ and
$S^{\prime}\cap\\{x_{i},y_{i}\\}\neq\emptyset$ for each $i\in\\{1,2,\ldots
a\\}$; without loss of generality let
$S_{0}=\cup_{i=1}^{a}\\{x_{i}\\}\subseteq S\cap S^{\prime}$.

First, we show that $\dim_{k}(G-e)=a+1$. Since
$r_{k,S_{0}}(z_{i})=r_{k,S_{0}}(z^{\prime}_{i})$ for each
$i\in\\{1,2,\ldots,a\\}$ in $G-e$, $|S|\geq a+1$, and hence $\dim_{k}(G-e)\geq
a+1$. Since $S_{0}\cup\\{v\\}$ forms a distance-$k$ resolving set of $G-e$,
$\dim_{k}(G-e)\leq a+1$. So, $\dim_{k}(G-e)=a+1$.

Second, we show that $\dim_{k}(G)=2a$. Note that, for each
$i\in\\{1,2,\ldots,a\\}$, $r_{k,S_{0}}(z_{i})=r_{k,S_{0}}(z^{\prime}_{i})$ in
$G$ and $R_{k}\\{z_{i},z^{\prime}_{i}\\}=\\{z_{i},z^{\prime}_{i},t_{i}\\}$;
thus, $S^{\prime}\cap\\{z_{i},z^{\prime}_{i},t_{i}\\}\neq\emptyset$ for each
$i\in\\{1,2,\ldots,a\\}$. So, $|S^{\prime}|\geq 2a$, and hence
$\dim_{k}(G)\geq 2a$. Since $S_{0}\cup(\cup_{i=1}^{a}\\{z_{i}\\})$ forms a
distance-$k$ resolving set of $G$, $\dim_{k}(G)\leq 2a$. Thus,
$\dim_{k}(G)=2a$.

Therefore, $\dim_{k}(G)-\dim_{k}(G-e)=2a-(a+1)=a-1\rightarrow\infty$ as
$a\rightarrow\infty$. ∎

$x_{1}$$y_{1}$$x_{2}$$y_{2}$$x_{a}$$y_{a}$$t_{1}$$t_{2}$$t_{a}$$v$$z_{1}$$z_{2}$$z_{a}$$e$
Figure 4: Graphs $G$ such that $\dim_{k}(G)-\dim_{k}(G-e)$ can be arbitrarily
large, where $k\geq 2$ and $a\geq 2$.

## References

  * [1] A.F. Beardon and J.A. Rodríguez-Velázquez, On the k-metric dimension of metric spaces. Ars Math. Contemp. 16 (2019) 25-38.
  * [2] P.S. Buczkowski, G. Chartrand, C. Poisson and P. Zhang, On $k$-dimensional graphs and their bases. Period. Math. Hungar. 46 (2003) 9-15.
  * [3] J. Cáceres, C. Hernando, M. Mora, I.M. Pelayo, M.L. Puertas and C. Seara, On the metric dimension of some families of graphs. Electron. Notes Discrete Math. 22 (2005) 129-133.
  * [4] J. Cáceres, C. Hernando, M. Mora, I.M. Pelayo, M.L. Puertas, C. Seara and D.R. Wood, On the metric dimension of Cartesian products of graphs. SIAM J. Discrete Math. 21(2) (2007) 423-441.
  * [5] G. Chartrand, L. Eroh, M.A. Johnson and O.R. Oellermann, Resolvability in graphs and the metric dimension of a graph. Discrete Appl. Math. 105 (2000) 99-113.
  * [6] L. Eroh, P. Feit, C.X. Kang and E. Yi, The effect of vertex or edge deletion on the metric dimension of graphs. J. Comb. 6(4) (2015) 433-444.
  * [7] L. Eroh, C.X. Kang and E. Yi, Metric dimension and zero forcing number of two families of line graphs. Math Bohem. 139(3) (2014) 467-483.
  * [8] L. Eroh, C.X. Kang and E. Yi, The connected metric dimension at a vertex of a graph. Theoret. Comput. Sci. 806 (2020) 53-69.
  * [9] A. Estrada-Moreno, On the (k, t)-metric dimension of a graph. Doctoral Thesis (2016)
  * [10] A. Estrada-Moreno, I.G. Yero and J.A. Rodríguez-Velázquez, On the (k, t)-metric dimension of graphs. The Computer Journal 64 (2021) 707-720.
  * [11] H. Fernau and J.A. Rodríguez-Velázquez, On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results. Discrete Appl. Math. 236 (2018) 183-202.
  * [12] M.R. Garey and D.S. Johnson, Computers and intractability: A guide to the theory of NP-completeness. Freeman, New York, 1979.
  * [13] J. Geneson, Metric dimension and pattern avoidance in graphs. Discrete Appl. Math. 284 (2020) 1-7.
  * [14] J. Geneson and E. Yi, Broadcast dimension of graphs (2020) https://arxiv.org/abs/2005.07311
  * [15] F. Harary and R.A. Melter, On the metric dimension of a graph. Ars Combin. 2 (1976) 191-195.
  * [16] C. Hernando, M. Mora, I.M. Pelayo, C. Seara and D.R. Wood, Extremal graph theory for metric dimension and diameter. Electron. J. Combin. (2010) #R30.
  * [17] M. Jannesari and B. Omoomi, The metric dimension of the lexicographic product of graphs. Discrete Math. 312 (2012) 3349-3356.
  * [18] I. Javaid, M.T. Rahim and K. Ali, Families of regular graphs with constant metric dimension. Util. Math. 75 (2008) 21-33.
  * [19] S. Khuller, B. Raghavachari and A. Rosenfeld, Landmarks in graphs. Discrete Appl. Math. 70 (1996) 217-229.
  * [20] C. Poisson and P. Zhang, The metric dimension of unicyclic graphs. J. Combin. Math. Combin. Comput. 40 (2002) 17-32.
  * [21] S.W. Saputro, E.T. Baskoro, A.N.M. Salman and D. Suprijanto, The metric dimension of a complete $n$-partite graph and its Cartesian product with a path. J. Combin. Math. Combin. Comput. 71 (2009) 283-293.
  * [22] B. Shanmukha, B. Sooryanarayana and K.S. Harinath, Metric dimension of wheels. Far East J. Appl. Math. 8 (2002) 217-229.
  * [23] P.J. Slater, Leaves of trees. Congr. Numer. 14 (1975) 549-559.
  * [24] K. Wagner, Über eine Eigenschaft der ebenen Komplexe. Math. Ann. 114 (1937) 570-590.