# The fractional $k$-truncated metric dimension of graphs

Eunjeong Yi
Texas A&M University at Galveston, Galveston, TX 77553, USA
<EMAIL_ADDRESS>
###### Abstract

The metric dimension, $\dim(G)$, and the fractional metric dimension,
$\dim_{f}(G)$, of a graph $G$ have 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$. Let $k$ be a positive integer. For any $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 set $S\subseteq V(G)$ is a _$k$
-truncated resolving set_ of $G$ if $|S\cap R_{k}\\{x,y\\}|\geq 1$ for any
distinct $x,y\in V(G)$, and the _$k$ -truncated metric dimension_
$\dim_{k}(G)$ of $G$ is the minimum cardinality over all $k$-truncated
resolving sets of $G$. For a function $g$ defined on $V(G)$ and for
$U\subseteq V(G)$, let $g(U)=\sum_{s\in U}g(s)$. A real-valued function
$g:V(G)\rightarrow[0,1]$ is a _$k$ -truncated resolving function_ of $G$ if
$g(R_{k}\\{x,y\\})\geq 1$ for any distinct $x,y\in V(G)$, and the _fractional
$k$-truncated metric dimension_ $\dim_{k,f}(G)$ of $G$ is
$\min\\{g(V(G)):g\mbox{ is a $k$-truncated resolving function of }G\\}$. Note
that $\dim_{k,f}(G)$ reduces to $\dim_{k}(G)$ if the codomain of $k$-truncated
resolving functions is restricted to $\\{0,1\\}$, and
$\dim_{k,f}(G)=\dim_{f}(G)$ if $k$ is at least the diameter of $G$. In this
paper, we study the fractional $k$-truncated metric dimension of graphs. For
any connected graph $G$ of order $n\geq 2$, we show that
$1\leq\dim_{k,f}(G)\leq\frac{n}{2}$; we characterize $G$ satisfying
$\dim_{k,f}(G)$ equals $1$ and $\frac{n}{2}$, respectively. We examine
$\dim_{k,f}(G)$ of some graph classes. We also show the existence of non-
isomorphic graphs $G$ and $H$ such that $\dim_{k}(G)=\dim_{k}(H)$ and
$\dim_{k,f}(G)\neq\dim_{k,f}(H)$, and we examine the relation among $\dim(G)$,
$\dim_{f}(G)$, $\dim_{k}(G)$ and $\dim_{k,f}(G)$. We conclude the paper with
some open problems.

Keywords: metric dimension, fractional metric dimension, $k$-truncated metric
dimension, distance-$k$ dimension, fractional $k$-truncated metric dimension,
fractional distance-$k$ dimension, trees, cyles
2010 Mathematics Subject Classification: 05C12, 05C72, 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 minimum number of edges on a path connecting $x$
and $y$ in $G$. The _diameter_ , $\textnormal{diam}(G)$, of $G$ is
$\max\\{d(x,y):x,y\in V(G)\\}$. Let $\mathbb{Z}^{+}$ denote the set of
positive integers. For $k\in\mathbb{Z}^{+}$ and for two vertices $x,y\in
V(G)$, let $d_{k}(x,y)=\min\\{d(x,y),k+1\\}$.

Metric dimension, introduced in [14] and [22], 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 vertex subset $S\subseteq V(G)$ is a _resolving
set_ of $G$ if $|S\cap R\\{x,y\\}|\geq 1$ for any pair of distinct $x,y\in
V(G)$, and the _metric dimension_ $\dim(G)$ of $G$ is the minimum cardinality
over all resolving sets of $G$. For $k\in\mathbb{Z}^{+}$ 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 vertex subset $S\subseteq V(G)$ is a _$k$ -truncated resolving set_ (also
called 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 _$k$ -truncated metric
dimension_ (also called the distance-$k$ dimension) $\dim_{k}(G)$ of $G$ is
the minimum cardinality over all $k$-truncated resolving sets of $G$. Notice
that $\dim_{k}(G)=\dim(G)$ if $k\geq\textnormal{diam}(G)-1$. The metric
dimension of a metric space $(V,d_{k})$ is studied in [3]. The $k$-truncated
metric dimension corresponds to the $(1,k+1)$-metric dimension in [7, 8]. We
note that $\dim_{1}(G)$ is also called the adjacency dimension of $G$ in [16].
For detailed results on $\dim_{k}(G)$, we refer to [11]. It is known that
determining the metric dimension and the $k$-truncated metric dimension of a
general graph are NP-hard problems; see [8, 10, 12, 19].

The fractionalization of various graph parameters has been extensively studied
(see [21]). For definition and a formulation of fractional metric dimension as
the optimal solution to a linear programming problem by relaxing a condition
of the integer programming problem for metric dimension, see [5, 9]. The
fractional metric dimension of graphs was officially studied in [1]. For a
function $g$ defined on $V(G)$ and for $U\subseteq V(G)$, let $g(U)=\sum_{s\in
U}g(s)$. A real-valued function $g:V(G)\rightarrow[0,1]$ is a _resolving
function_ of $G$ if $g(R\\{x,y\\})\geq 1$ for any distinct vertices $x,y\in
V(G)$. The _fractional metric dimension_ , $\dim_{f}(G)$, of $G$ is
$\min\\{g(V(G)):g\mbox{ is a resolving function of }G\\}$. Notice that
$\dim_{f}(G)$ reduces to $\dim(G)$ if the codomain of resolving functions is
restricted to $\\{0,1\\}$.

For $k\in\mathbb{Z}^{+}$, a real-valued function $h:V(G)\rightarrow[0,1]$ is a
_$k$ -truncated resolving function_ (also called a distance-$k$ resolving
function) of $G$ if $h(R_{k}\\{x,y\\})\geq 1$ for any pair of distinct $x,y\in
V(G)$. The _fractional $k$-truncated metric dimension_ (also called the
fractional distance-$k$ dimension) of $G$, denoted by $\dim_{k,f}(G)$, is
$\min\\{h(V(G)):h\mbox{ is a $k$-truncated resolving function of }G\\}$. Note
that $\dim_{k,f}(G)=\dim_{k}(G)$ if the codomain of $k$-truncated resolving
functions is restricted to $\\{0,1\\}$, $\dim_{k,f}(G)=\dim_{f}(G)$ if
$k\geq\textnormal{diam}(G)-1$, and $\dim_{k,f}(G)=\dim(G)$ if
$k\geq\textnormal{diam}(G)-1$ and the codomain of $k$-truncated resolving
functions is restricted to $\\{0,1\\}$.

In this paper, we initiate the study of the fractional $k$-truncated metric
dimension of graphs. Let $P_{n}$, $C_{n}$ and $K_{n}$, respectively, denote
the path, the cycle and the complete graph on $n$ vertices. In Section 2, for
any connected graph $G$ of order $n\geq 2$ and for any $k\in\mathbb{Z}^{+}$,
we show that $1\leq\dim_{k,f}(G)\leq\frac{n}{2}$ and we characterize $G$
satisfying $\dim_{k,f}(G)$ equals $1$ and $\frac{n}{2}$, respectively. Along
the way, we state some useful observations. In Section 3, we examine
$\dim_{k,f}(G)$ when $G$ is the Petersen graph, a wheel graph, a fan graph, a
complete multipartite graph, a cycle, a grid graph or a tree. In Section 4, we
examine the relation among $\dim(G)$, $\dim_{f}(G)$, $\dim_{k}(G)$ and
$\dim_{k,f}(G)$. We show the existence of non-isomorphic graphs $G$ and $H$
such that $\dim_{k}(G)=\dim_{k}(H)$ and $\dim_{k,f}(G)\neq\dim_{k,f}(H)$.
Based on the construction in [13], we also show the existence of two connected
graphs $H$ and $G$ with $H\subset G$ such that
$\frac{\dim_{k,f}(H)}{\dim_{k,f}(G)}$ can be arbitrarily large. We conclude
the paper with some open problems.

##  2 Some observations and bounds on $\dim_{k,f}(G)$

In this section, for any connected graph $G$ of order $n\geq 2$ and for any
$k\in\mathbb{Z}^{+}$, we show that $1\leq\dim_{k,f}(G)\leq\frac{n}{2}$; we
characterize $G$ satisfying $\dim_{k,f}(G)$ equals $1$ and $\frac{n}{2}$,
respectively.

We begin with some observations. For $v\in V(G)$, let $N(v)=\\{w\in V(G):vw\in
E(G)\\}$ and $N[v]=N(v)\cup\\{v\\}$. More generally, for $k\in\mathbb{Z}^{+}$
and for $v\in V(G)$, let $N_{k}[v]=\\{w\in V(G):d(v,w)\leq k\\}$ and
$N_{k}(v)=\\{w\in V(G):d(v,w)=k\\}$. Two vertices $x,y\in V(G)$ are called
_twins_ if $N(x)-\\{y\\}=N(y)-\\{x\\}$. Hernando et al. [15] observed that the
twin relation is an equivalence relation and that an equivalence class under
it, called a twin equivalence class, induces either a clique or an
independence set.

######  Observation 2.1.

Let $x,y\in V(G)$ with $x\neq y$, and let $k\in\mathbb{Z}^{+}$.

  * (a)

_[24]_ If $x$ and $y$ are twins, then $g(x)+g(y)\geq 1$ for any resolving
function $g$ of $G$.

  * (b)

If $x$ and $y$ are twins, then $h(x)+h(y)\geq 1$ for any $k$-truncated
resolving function $h$ of $G$.

  * (c)

For any $k\geq 1$, $R_{k}\\{x,y\\}=(N_{k}[x]\cup
N_{k}[y])-\cup_{i=1}^{k}(N_{i}(x)\cap N_{i}(y))$.

######  Observation 2.2.

Let $G$ be a non-trivial connected graph, and let
$k,k^{\prime}\in\mathbb{Z}^{+}$. Then

  * (a)

_[1]_ $\dim_{f}(G)\leq\dim(G)$;

  * (b)

_[3, 7]_ if $k>k^{\prime}$, then
$\dim(G)\leq\dim_{k}(G)\leq\dim_{k^{\prime}}(G)\leq\dim_{1}(G)$;

  * (c)

$\dim_{f}(G)\leq\dim_{k,f}(G)\leq\dim_{k}(G)$;

  * (d)

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

######  Observation 2.3.

Let $G$ be a connected graph with $\textnormal{diam}(G)=d$, and let
$k\in\mathbb{Z}^{+}$.

  * (a)

_[7]_ If $k\geq d-1$, then $\dim_{k}(G)=\dim(G)$.

  * (b)

If $k\geq d-1$, then $\dim_{k,f}(G)=\dim_{f}(G)$.

Next, we recall some results involving the bounds of the $k$-truncated metric
dimension and the fractional metric dimension of graphs.

######  Theorem 2.4.

Let $G$ be a connected graph of order $n\geq 2$, and let $k\in\mathbb{Z}^{+}$.
Then

  * (a)

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

  * (b)

_[1, 17]_ $1\leq\dim_{f}(G)\leq\frac{n}{2}$, and $\dim_{f}(G)=\frac{n}{2}$ if
and only if there exists a bijection $\phi:V(G)\rightarrow V(G)$ such that
$\phi(v)\neq v$ and $|R\\{v,\phi(v)\\}|=2$ for all $v\in V(G)$;

  * (c)

_[18]_ $\dim_{f}(G)=1$ if and only if $G=P_{n}$.

For the characterization of connected graphs $G$ of order $n$ satisfying
$\dim_{k}(G)=n-2$ and $\dim_{k}(G)=n-1$ respectively, see [11, 23]. For an
explicit characterization of graphs $G$ satisfying
$\dim_{f}(G)=\frac{|V(G)|}{2}$, we recall the following construction from [2].
Let $\mathcal{K}=\\{K_{a}:a\geq 2\\}$ and
$\overline{\mathcal{K}}=\\{\overline{K}_{b}:b\geq 2\\}$, where $\overline{G}$
denotes the complement of a graph $G$. Let
$H[\mathcal{K}\cup\overline{\mathcal{K}}]$ be the family of graphs obtained
from a connected graph $H$ by replacing each vertex $u_{i}\in V(H)$ by a graph
$H_{i}\in\mathcal{K}\cup\overline{\mathcal{K}}$, and each vertex in $H_{i}$ is
adjacent to each vertex in $H_{j}$ if and only if $u_{i}u_{j}\in E(H)$.

######  Theorem 2.5.

_[2]_ Let $G$ be a connected graph of order at least two. Then
$\dim_{f}(G)=\frac{|V(G)|}{2}$ if and only if $G\in
H[\mathcal{K}\cup\overline{\mathcal{K}}]$ for some connected graph $H$.

Next, we obtain the bounds on $\dim_{k,f}(G)$.

######  Proposition 2.6.

For any connected graph $G$ of order $n\geq 2$ and for any
$k\in\mathbb{Z}^{+}$, $1\leq\dim_{k,f}(G)\leq\frac{n}{2}$.

###### Proof.

Let $k\in\mathbb{Z}^{+}$, and let $G$ be a connected graph of order $n\geq 2$.
By definition, $\dim_{k,f}(G)\geq 1$. If $g:V(G)\rightarrow[0,1]$ is a
function defined by $g(v)=\frac{1}{2}$ for each $v\in V(G)$, then
$R_{k}\\{x,y\\}\supseteq\\{x,y\\}$ and $g(R_{k}\\{x,y\\})\geq g(x)+g(y)=1$ for
any distinct $x,y\in V(G)$; thus, $g$ is a $k$-truncated resolving function of
$G$ with $g(V(G))=\frac{n}{2}$. So, $\dim_{k,f}(G)\leq\frac{n}{2}$. ∎

Next, we characterize connected graphs $G$ satisfying $\dim_{k,f}(G)=1$ for
any $k\in\mathbb{Z}^{+}$.

######  Theorem 2.7.

Let $G$ be a non-trivial connected graph, and let $k\in\mathbb{Z}^{+}$. Then
$\dim_{k,f}(G)=1$ if and only if $G\in\cup_{i=2}^{k+2}\\{P_{i}\\}$.

###### Proof.

Let $G$ be a connected graph of order $n\geq 2$, and let $k\in\mathbb{Z}^{+}$.

($\Leftarrow$) Let $G\in\cup_{i=2}^{k+2}\\{P_{i}\\}$. Then
$1=\dim_{f}(G)\leq\dim_{k,f}(G)\leq\dim_{k}(G)=1$ by Observation 2.2(c) and
Theorem 2.4(a)(c). So, $\dim_{k,f}(G)=1$.

($\Rightarrow$) Let $\dim_{k,f}(G)=1$. By Observation 2.2(c) and Theorem
2.4(c), $\dim_{k,f}(G)\geq\dim_{f}(G)\geq 1$ and $\dim_{f}(G)=1$ if and only
if $G=P_{n}$. So, if $G\neq P_{n}$, then $\dim_{k,f}(G)>1$. Now, suppose
$G=P_{n}$, and let $P_{n}$ be a path given by $u_{1},u_{2},\ldots,u_{n}$. Let
$g:V(P_{n})\rightarrow[0,1]$ be any minimum $k$-truncated resolving function
of $P_{n}$. If $n\leq k+2$, then $\dim_{k,f}(P_{n})=1$ as shown above. So,
suppose $n\geq k+3$; we show that $\dim_{k,f}(P_{n})>1$.

First, let $k+3\leq n\leq 2k+3$. Then
$R_{k}\\{u_{1},u_{2}\\}=\cup_{i=1}^{k+2}\\{u_{i}\\}$,
$R_{k}\\{u_{n-1},u_{n}\\}=\cup_{i=n-(k+1)}^{n}\\{u_{i}\\}$, and
$R_{k}\\{u_{i-1},u_{i+1}\\}=V(P_{n})-\\{u_{i}\\}$ for each
$i\in\\{n-(k+1),\ldots,k+2\\}$. So,
$g(R_{k}\\{u_{1},u_{2}\\})\geq\sum_{i=1}^{k+1}g(u_{i})\geq 1$,
$g(R_{k}\\{u_{n-1},u_{n}\\})\geq\sum_{i=n-(k+1)}^{n}g(u_{i})\geq 1$, and
$g(R_{k}\\{u_{i-1},u_{i+1}\\})=g(V(P_{n}))-g(u_{i})\geq 1$ for each
$i\in\\{n-(k+1),\ldots,k+2\\}$. By summing over the $(6+2k-n)$ inequalities,
we have $(5+2k-n)g(V(P_{n}))\geq 6+2k-n$, i.e.,
$g(V(P_{n}))\geq\frac{6+2k-n}{5+2k-n}$; thus,
$\dim_{k,f}(P_{n})\geq\frac{6+2k-n}{5+2k-n}>1$ (also see Theorem 3.11(b)).

Second, let $n\geq 2k+4$. Then
$R_{k}\\{u_{1},u_{2}\\}=\cup_{i=1}^{k+2}\\{u_{i}\\}$ and
$R_{k}\\{u_{n-1},u_{n}\\}=\cup_{i=n-k-1}^{n}\\{u_{i}\\}$. So,
$g(R_{k}\\{u_{1},u_{2}\\})=\sum_{i=1}^{k+2}g(u_{i})\geq 1$ and
$g(R_{k}\\{u_{n-1},u_{n}\\})=\sum_{i=n-k-1}^{n}g(u_{i})\geq 1$. Since
$n-k-1\geq 2k+4-k-1=k+3$,
$g(V(P_{n}))\geq\sum_{i=1}^{k+2}g(u_{i})+\sum_{i=n-k-1}^{n}g(u_{i})\geq 2$,
which implies $\dim_{k,f}(P_{n})\geq 2$. ∎

Next, via a proof technique used in [2], we characterize connected graphs $G$
satisfying $\dim_{k,f}(G)=\frac{|V(G)|}{2}$ for any $k\in\mathbb{Z}^{+}$.

######  Theorem 2.8.

Let $G$ be a connected graph of order $n\geq 2$. Then
$\dim_{1,f}(G)=\frac{n}{2}$ if and only if $G\in
H[\mathcal{K}\cup\overline{\mathcal{K}}]$ for some connected graph $H$.

###### Proof.

Let $G$ be a connected graph of order $n\geq 2$.

($\Leftarrow$) Let $G\in H[\mathcal{K}\cup\overline{\mathcal{K}}]$ for some
connected graph $H$. Then $\dim_{1,f}(G)\geq\dim_{f}(G)=\frac{n}{2}$ by
Observation 2.2(d) and Theorem 2.5. Since $\dim_{1,f}(G)\leq\frac{n}{2}$ by
Proposition 2.6, $\dim_{1,f}(G)=\frac{n}{2}$.

($\Rightarrow$) Let $\dim_{1,f}(G)=\frac{n}{2}$. It suffices to show that each
twin equivalence class of $V(G)$ has cardinality at least two. Assume, to the
contrary, that there exists a twin equivalence class $Q\subset V(G)$
consisting of exactly one element; let $z\in Q$. Let $h:V(G)\rightarrow[0,1]$
be a function defined by $h(z)=0$ and $h(v)=\frac{1}{2}$ for each $v\in
V(G)-\\{z\\}$. Since $|R_{1}\\{z,u\\}|\geq 3$ for any $u\in V(G)-\\{z\\}$, $h$
is a $1$-truncated resolving function of $G$ with $h(V(G))=\frac{n-1}{2}$, and
hence $\dim_{1,f}(G)\leq\frac{n-1}{2}$, a contradiction. So, each twin
equivalence class of $V(G)$ must have cardinality at least two. By the
connectedness of $G$, we conclude that $G\in
H[\mathcal{K}\cup\overline{\mathcal{K}}]$ for some connected graph $H$. ∎

Since $\dim_{f}(G)\leq\dim_{k,f}(G)\leq\dim_{1,f}(G)$ by Observation 2.2(d),
Theorems 2.5 and 2.8 imply the following

######  Corollary 2.9.

Let $G$ be a connected graph of order $n\geq 2$, and let $k\in\mathbb{Z}^{+}$.
Then $\dim_{k,f}(G)=\frac{n}{2}$ if and only if $G\in
H[\mathcal{K}\cup\overline{\mathcal{K}}]$ for some connected graph $H$.

##  3 $\dim_{k,f}(G)$ of some graph classes

In this section, we examine $\dim_{k,f}(G)$ for some classes of graphs.

We recall some terminology. The _join_ of two graphs $G$ and $H$, denoted by
$G+H$, is the graph obtained from the disjoint union of $G$ and $H$ by joining
an edge between each vertex of $G$ and each vertex of $H$.

The _degree_ of a vertex $v\in V(G)$ is $|N(v)|$; a _leaf_ is a vertex of
degree one and a _major vertex_ is a vertex of degree at least three. Now, fix
a tree $T$. A leaf $\ell$ is called a _terminal vertex_ of a major vertex $v$
if $d(\ell,v)<d(\ell,w)$ for every other major vertex $w$ in $T$. The
_terminal degree_ , $ter(v)$, of a major vertex $v$ is the number of terminal
vertices of $v$ in $T$, and an _exterior major vertex_ is a major vertex that
has positive terminal degree. Let $M(T)$ be the set of exterior major vertices
of $T$ and let $L(T)$ be the set of leaves of $T$. Let $M_{1}(T)=\\{w\in
M(T):ter(w)=1\\}$, $M_{2}(T)=\\{w\in M(T):ter(w)\geq 2\\}$; then
$M(T)=M_{1}(T)\cup M_{2}(T)$. Let $\sigma(T)=|L(T)|$, $ex(T)=|M(T)|$ and
$ex_{1}(T)=|M_{1}(T)|$.

Now, we recall the fractional metric dimension of some classes of graphs.

######  Theorem 3.1.

  * (a)

_[24]_ For any tree $T$, $\dim_{f}(T)=\frac{1}{2}(\sigma(T)-ex_{1}(T))$.

  * (b)

_[1]_ For the Petersen graph $\mathcal{P}$,
$\dim_{f}(\mathcal{P})=\frac{5}{3}$.

  * (c)

_[1]_ For $n\geq 3$,
$\dim_{f}(C_{n})=\left\\{\begin{array}[]{ll}\frac{n}{n-1}&\mbox{if $n$ is
odd},\\\ \frac{n}{n-2}&\mbox{if $n$ is even}.\end{array}\right.$

  * (d)

_[1]_ For the wheel graph $W_{n}=C_{n-1}+K_{1}$ of order $n\geq 5$,
$\dim_{f}(W_{n})=\left\\{\begin{array}[]{ll}2&\mbox{if }n=5,\\\
\frac{3}{2}&\mbox{if }n=6,\\\ \frac{n-1}{4}&\mbox{if }n\geq
7.\end{array}\right.$

  * (e)

_[24]_ 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}$, and let $s$ be the number
of partite sets of $G$ consisting of exactly one element. Then

$\dim_{f}(G)=\left\\{\begin{array}[]{ll}\frac{n-1}{2}&\mbox{if }s=1,\\\
\frac{n}{2}&\mbox{otherwise}.\end{array}\right.$

  * (f)

_[1]_ For the grid graph $G=P_{s}\times P_{t}$ ($s,t\geq 2$), $\dim_{f}(G)=2$.

###  3.1 Graphs $G$ with $\textnormal{diam}(G)\leq 2$

If $G$ is a graph with $\textnormal{diam}(G)\leq 2$, then
$\dim_{k,f}(G)=\dim_{f}(G)$ for any $k\in\mathbb{Z}^{+}$. So, for any
$k\in\mathbb{Z}^{+}$, we have $\dim_{k,f}(C_{n}+K_{1})=\dim_{f}(C_{n}+K_{1})$,
$\dim_{k,f}(P_{n}+K_{1})=\dim_{f}(P_{n}+K_{1})$,
$\dim_{k,f}(\mathcal{P})=\dim_{f}(\mathcal{P})$ for the Petersen graph
$\mathcal{P}$, and $\dim_{k,f}(G)=\dim_{f}(G)$ for any complete multipartite
graph $G$, for examples. So, Theorem 3.1(b)(d)(e) implies the following.

######  Corollary 3.2.

Let $k\in\mathbb{Z}^{+}$.

  * (a)

For the Petersen graph $\mathcal{P}$, $\dim_{k,f}(\mathcal{P})=\frac{5}{3}$.

  * (b)

For $n\geq 3$,

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

  * (c)

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_{k,f}(G)=\left\\{\begin{array}[]{ll}\frac{n-1}{2}&\mbox{if }s=1,\\\
\frac{n}{2}&\mbox{otherwise}.\end{array}\right.$

Next, we examine $\dim_{k,f}(P_{n}+K_{1})$.

######  Theorem 3.3.

Let $k\in\mathbb{Z}^{+}$.

  * (a)

For $n\geq 1$,

$\dim_{k,f}(P_{n}+K_{1})=\dim_{f}(P_{n}+K_{1})=\left\\{\begin{array}[]{ll}\frac{n+1}{2}&\mbox{
if }n\in\\{1,2,3\\},\\\ \frac{5}{3}&\mbox{ if }n\in\\{4,5\\},\\\
\frac{n+1}{4}&\mbox{ if }n\geq 6\mbox{ and }n\equiv 1,3\pmod{4},\\\
\frac{n+2}{4}&\mbox{ if }n\geq 6\mbox{ and }n\equiv
2\pmod{4}.\end{array}\right.$

  * (b)

If $n\geq 8$ and $n\equiv 0\pmod{4}$, then
$\frac{n}{4}\leq\dim_{k,f}(P_{n}+K_{1})=\dim_{f}(P_{n}+K_{1})\leq\frac{n+2}{4}$.

###### Proof.

Let $k\in\mathbb{Z}^{+}$ and $n\geq 1$. Since
$\textnormal{diam}(P_{n}+K_{1})\leq 2$,
$\dim_{k,f}(P_{n}+K_{1})=\dim_{f}(P_{n}+K_{1})$ by Observation 2.3(b). Let
$G=P_{n}+K_{1}$ such that $P_{n}$ is given by $u_{1},u_{2},\ldots,u_{n}$ and
$w$ is the vertex in $K_{1}$. Let $g:V(G)\rightarrow[0,1]$ be any minimum
($k$-truncated) resolving function of $G$.

First, let $n\in\\{1,2\\}$; then $P_{n}+K_{1}=K_{n+1}$ and
$\dim_{k,f}(P_{n}+K_{1})=\dim_{f}(P_{n}+K_{1})=\frac{n+1}{2}$ by Theorem
3.1(e). Second, let $n=3$. Since $u_{1}$ and $u_{3}$ are twins and $u_{2}$ and
$w$ are twins in $G$, $g(u_{1})+g(u_{3})\geq 1$ and $g(u_{2})+g(w)\geq 1$ by
Observation 2.1(a)(b); thus $g(V(G))\geq 2$, and hence
$\dim_{k,f}(G)=\dim_{f}(G)\geq 2$. By Theorem 2.4(b),
$\dim_{k,f}(G)=\dim_{f}(G)=2$.

Third, let $n=4$. Then
$R_{k}\\{u_{1},u_{2}\\}=R\\{u_{1},u_{2}\\}=V(G)-\\{w,u_{4}\\}$,
$R_{k}\\{u_{1},u_{3}\\}=R\\{u_{1},u_{3}\\}=V(G)-\\{w,u_{2}\\}$,
$R_{k}\\{u_{2},u_{4}\\}=R\\{u_{2},u_{4}\\}=V(G)-\\{w,u_{3}\\}$,
$R_{k}\\{u_{3},u_{4}\\}=R\\{u_{3},u_{4}\\}=V(G)-\\{w,u_{1}\\}$,
$R_{k}\\{u_{2},w\\}=R\\{u_{2},w\\}=V(G)-\\{u_{1},u_{3}\\}$, and
$R_{k}\\{u_{3},w\\}=R\\{u_{3},w\\}=V(G)-\\{u_{2},u_{4}\\}$. So,
$g(V(G))-g(w)-g(u_{4})\geq 1$, $g(V(G))-g(w)-g(u_{2})\geq 1$,
$g(V(G))-g(w)-g(u_{3})\geq 1$, $g(V(G))-g(w)-g(u_{1})\geq 1$,
$3g(V(G))-3g(u_{1})-3g(u_{3})\geq 3$ and $3g(V(G))-3g(u_{2})-3g(u_{4})\geq 3$.
By summing over the six inequalities, we have $6g(V(G))\geq 10$; thus,
$\dim_{k,f}(G)=\dim_{f}(G)\geq\frac{5}{3}$. On the other hand, if
$h:V(G)\rightarrow[0,1]$ is a function defined by $h(w)=h(u_{i})=\frac{1}{3}$
for each $i\in\\{1,2,3,4\\}$, then $h$ is a ($k$-truncated) resolving function
of $G$ with $h(V(G))=\frac{5}{3}$; thus
$\dim_{k,f}(G)=\dim_{f}(G)\leq\frac{5}{3}$. Therefore,
$\dim_{k,f}(G)=\dim_{f}(G)=\frac{5}{3}$.

Fourth, let $n=5$. Then
$R_{k}\\{u_{1},u_{2}\\}=R\\{u_{1},u_{2}\\}=V(G)-\\{w,u_{4},u_{5}\\}$,
$R_{k}\\{u_{4},u_{5}\\}=R\\{u_{4},u_{5}\\}=V(G)-\\{w,u_{1},u_{2}\\}$,
$R_{k}\\{u_{2},w\\}=R\\{u_{2},w\\}=V(G)-\\{u_{1},u_{3}\\}$,
$R_{k}\\{u_{3},w\\}=R\\{u_{3},w\\}=V(G)-\\{u_{2},u_{4}\\}$ and
$R_{k}\\{u_{4},w\\}=R\\{u_{4},w\\}=V(G)-\\{u_{3},u_{5}\\}$. So,
$g(V(G))-g(w)-g(u_{4})-g(u_{5})\geq 1$, $g(V(G))-g(w)-g(u_{1})-g(u_{2})\geq
1$, $g(V(G))-g(u_{1})-g(u_{3})\geq 1$, $g(V(G))-g(u_{2})-g(u_{4})\geq 1$ and
$g(V(G))-g(u_{3})-g(u_{5})\geq 1$. By summing over the five inequalities, we
have $3g(V(G))\geq 5$; thus, $\dim_{k,f}(G)=\dim_{f}(G)\geq\frac{5}{3}$. On
the other hand, if $h:V(G)\rightarrow[0,1]$ is a function defined by $h(w)=0$
and $h(u_{i})=\frac{1}{3}$ for each $i\in\\{1,2,3,4,5\\}$, then $h$ is a
($k$-truncated) resolving function of $G$ with $h(V(G))=\frac{5}{3}$; thus
$\dim_{k,f}(G)=\dim_{f}(G)\leq\frac{5}{3}$. Therefore,
$\dim_{k,f}(G)=\dim_{f}(G)=\frac{5}{3}$.

Next, let $n\geq 6$, and we consider the following cases.

_Case 1: $n\equiv 1,3\pmod{4}$._ In this case, $n$ is odd; let $n=2x+1$, where
$x\geq 3$. Note that
$R_{k}\\{u_{1},u_{2}\\}=R\\{u_{1},u_{2}\\}=\\{u_{1},u_{2},u_{3}\\}$,
$R_{k}\\{u_{2x},u_{2x+1}\\}=R\\{u_{2x},u_{2x+1}\\}=\\{u_{2x-1},u_{2x},u_{2x+1}\\}$,
and
$R_{k}\\{u_{i-1},u_{i+1}\\}=R\\{u_{i-1},u_{i+1}\\}=\\{u_{i-2},u_{i-1},u_{i+1},u_{i+2}\\}$
for each odd $i\in\\{3,5,\ldots,2x-1\\}$. So, $g(u_{1})+g(u_{2})+g(u_{3})\geq
1$, $g(u_{2x-1})+g(u_{2x})+g(u_{2x+1})\geq 1$, and
$g(u_{i-2})+g(u_{i-1})+g(u_{i+1})+g(u_{i+2})\geq 1$ for each odd
$i\in\\{3,5,\ldots,2x-1\\}$. By summing over the $x+1$ inequalities, we have
$2g(V(G))\geq 2\sum_{i=1}^{2x+1}g(u_{i})\geq x+1$, and thus
$\dim_{k,f}(G)=\dim_{f}(G)\geq\frac{x+1}{2}=\frac{n+1}{4}$. Now, let
$h:V(G)\rightarrow[0,1]$ be a function defined by $h(u_{i})=\frac{1}{2}$ if
$i$ is odd, and $h(w)=h(u_{i})=0$ if $i$ is even. Then $h$ is a
($k$-truncated) resolving function of $G$ with $h(V(G))=\frac{x+1}{2}$ since
$|R\\{u_{i},u_{j}\\}\cap(\cup_{\alpha=1}^{x+1}\\{u_{2\alpha-1}\\})|\geq 2$ and
$|R\\{u_{i},w\\}\cap(\cup_{\alpha=1}^{x+1}\\{u_{2\alpha-1}\\})|\geq 2$. So,
$\dim_{k,f}(G)=\dim_{f}(G)\leq\frac{x+1}{2}=\frac{n+1}{4}$. Thus,
$\dim_{k,f}(G)=\dim_{f}(G)=\frac{n+1}{4}$ for $n\equiv 1,3\pmod{4}$.

_Case 2: $n\equiv 2\pmod{4}$._ Let $n=4x+2$, where $x\geq 1$. Since
$R_{k}\\{u_{1},u_{2}\\}=R\\{u_{1},u_{2}\\}=\\{u_{1},u_{2},u_{3}\\}$,
$R_{k}\\{u_{4x+1},u_{4x+2}\\}=R\\{u_{4x+1},u_{4x+2}\\}=\\{u_{4x},u_{4x+1},u_{4x+2}\\}$,
and
$R_{k}\\{u_{4i+1},u_{4i+2}\\}=R\\{u_{4i+1},u_{4i+2}\\}=\\{u_{4i},u_{4i+1},u_{4i+2},u_{4i+3}\\}$
for each $i\in\\{1,2,\ldots,x-1\\}$, we have $g(u_{1})+g(u_{2})+g(u_{3})\geq
1$, $g(u_{4x})+g(u_{4x+1})+g(u_{4x+2})\geq 1$, and
$g(u_{4i})+g(u_{4i+1})+g(u_{4i+2})+g(u_{4i+3})\geq 1$ for each
$i\in\\{1,2,\ldots,x-1\\}$. By summing over the $x+1$ inequalities, we have
$g(V(G))\geq\sum_{i=1}^{4x+2}g(u_{i})\geq x+1=\frac{n+2}{4}$; thus,
$\dim_{k,f}(G)=\dim_{f}(G)\geq\frac{n+2}{4}$. If we let
$h:V(G)\rightarrow[0,1]$ be a function defined by $h(w)=0$,
$h(u_{1})=h(u_{4x+2})=\frac{1}{2}$, and $h(u_{j})=\frac{1}{4}$ for each
$j\in\\{2,3,\ldots,4x+1\\}$, then $h$ is a ($k$-truncated) resolving function
of $G$ with $h(V(G))=\frac{n+2}{4}$; thus
$\dim_{k,f}(G)=\dim_{f}(G)\leq\frac{n+2}{4}$. Therefore,
$\dim_{k,f}(G)=\dim_{f}(G)=\frac{n+2}{4}$ for $n\equiv 2\pmod{4}$.

_Case 3: $n\equiv 0\pmod{4}$._ Let $n=4x$, where $x\geq 2$. For each
$i\in\\{0,1,\ldots,x-1\\}$,
$R_{k}\\{u_{4i+2},u_{4i+3}\\}=R\\{u_{4i+2},u_{4i+3}\\}=\\{u_{4i+1},u_{4i+2},u_{4i+3},u_{4i+4}\\}$
and $g(u_{4i+1})+g(u_{4i+2})+g(u_{4i+3})+g(u_{4i+4})\geq 1$. By summing over
the $x$ inequalities, we have $g(V(G))\geq\sum_{i=1}^{4x}g(u_{i})\geq x$;
thus, $\dim_{k,f}(G)=\dim_{f}(G)\geq\frac{n}{4}$. If we let
$h:V(G)\rightarrow[0,1]$ be a function defined by $h(w)=0$,
$h(u_{1})=\frac{1}{2}=h(u_{4x})$, and $h(u_{i})=\frac{1}{4}$ for each
$i\in\\{2,3,\ldots,4x-1\\}$, then $h$ is a ($k$-truncated) resolving function
of $G$ with $g(V(G))=\frac{n+2}{4}$; thus,
$\dim_{k,f}(G)=\dim_{f}(G)\leq\frac{n+2}{4}$. So,
$\frac{n}{4}\leq\dim_{k,f}(G)=\dim_{f}(G)\leq\frac{n+2}{4}$ for $n\equiv
0\pmod{4}$. ∎

###  3.2 Cycles

We determine $\dim_{k,f}(C_{n})$ for any $k\in\mathbb{Z}^{+}$ and for $n\geq
3$.

######  Theorem 3.4.

For any $k\in\mathbb{Z}^{+}$ and for $n\geq 3$,

$\dim_{k,f}(C_{n})=\left\\{\begin{array}[]{ll}\frac{n}{n-1}&\mbox{ if }n\leq
2k+3\mbox{ and $n$ is odd},\\\ \frac{n}{n-2}&\mbox{ if }n\leq 2k+3\mbox{ and
$n$ is even},\\\ \frac{n}{2(k+1)}&\mbox{ if }n\geq 2k+4.\end{array}\right.$

###### Proof.

Let $k\in\mathbb{Z}^{+}$. For $n\geq 3$, let $C_{n}$ be given by
$u_{0},u_{1},\ldots,u_{n-1},u_{0}$. Let $g:V(C_{n})\rightarrow[0,1]$ be any
minimum $k$-truncated resolving function of $C_{n}$.

First, let $n\leq 2k+3$; then
$\textnormal{diam}(C_{n})\leq\lfloor\frac{2k+3}{2}\rfloor=k+1$. By Observation
2.3(b), $\dim_{k,f}(C_{n})=\dim_{f}(C_{n})$. So, by Theorem 3.1(c),
$\dim_{k,f}(C_{n})=\frac{n}{n-1}$ for an odd $n$ and
$\dim_{k,f}(C_{n})=\frac{n}{n-2}$ for an even $n$.

Second, let $n\geq 2k+4$. Note that, for each $i\in\\{0,1,\ldots,n-1\\}$,
$R_{k}\\{u_{i},u_{i+2}\\}=\cup_{j=0}^{k}\\{u_{i-j},u_{i+2+j}\\}$, where the
subscript it taken modulo $n$; thus
$\sum_{j=0}^{k}(g(u_{i-j})+g(u_{i+2+j}))\geq 1$. By summing over $n$ such
inequalities, we have $2(k+1)g(V(C_{n}))\geq n$ since each vertex appears
$2(k+1)$ times in the $n$ inequalities. So, $g(V(C_{n}))\geq\frac{n}{2(k+1)}$,
and hence $\dim_{k,f}(C_{n})\geq\frac{n}{2(k+1)}$. On the other hand, if we
let $h:V(C_{n})\rightarrow[0,1]$ be a function defined by
$h(u_{i})=\frac{1}{2(k+1)}$ for each $i\in\\{0,1,\ldots,n-1\\}$, then $h$ is a
$k$-truncated resolving function of $C_{n}$ with
$h(V(C_{n}))=\frac{n}{2(k+1)}$. To see this, for any distinct
$x,y\in\\{0,1,\ldots,n-1\\}$, note that $|R_{k}\\{u_{x},u_{y}\\}|\geq 2(k+1)$
and $h(R_{k}\\{u_{x},u_{y}\\})\geq\frac{1}{2(k+1)}\cdot 2(k+1)=1$. So,
$\dim_{k,f}(C_{n})\leq h(V(C_{n}))=\frac{n}{2(k+1)}$. Therefore,
$\dim_{k,f}(C_{n})=\frac{n}{2(k+1)}$. ∎

Theorem 3.4 implies the following

######  Corollary 3.5.

For $n\geq 3$,

$\dim_{1,f}(C_{n})=\left\\{\begin{array}[]{ll}\frac{n}{2}&\mbox{ if
}n\in\\{3,4\\},\\\ \frac{n}{4}&\mbox{ if }n\geq 5.\end{array}\right.$

###  3.3 Grid graphs

We examine $\dim_{k,f}(P_{s}\times P_{t})$ for $s,t\geq 2$. We show that, for
some $k>1$, $\frac{\dim_{1,f}(G)}{\dim_{k,f}(G)}$ and
$\frac{\dim_{k,f}(G)}{\dim_{f}(G)}$ can be arbitrarily large. We also
characterize grid graphs $G$ satisfying $\dim_{1,f}(G)=\dim_{f}(G)$.

We recall some notations. Let $f(x)$ and $g(x)$ be functions defined on some
subset of real numbers. 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))$. We note that
$\frac{\dim_{1}(G)}{\dim(G)}$ can be arbitrarily large (see [13]) and that
both $\frac{\dim_{1}(G)}{\dim_{k}(G)}$ and $\frac{\dim_{k}(G)}{\dim(G)}$ can
be arbitrarily large for some $k>1$ (see [11]).

First, we show that $\frac{\dim_{1,f}(G)}{\dim_{k,f}(G)}$ and
$\frac{\dim_{k,f}(G)}{\dim_{f}(G)}$ can be arbitrarily large for some $k>1$.

######  Proposition 3.6.

_[13]_ If $G=P_{m}\times P_{m}$ for $m\geq 2$, then
$\dim_{1}(G)=\Theta(m^{2})$.

######  Proposition 3.7.

_[11]_ For some positive integer $k>1$, let $G=P_{k^{2}}\times P_{k^{2}}$.
Then $\dim_{k}(G)=\Theta(k^{2})$.

######  Proposition 3.8.

If $G=P_{4m}\times P_{3m}$ for $m\geq 1$, then $\dim_{1,f}(G)=\Theta(m^{2})$.

###### Proof.

By Proposition 3.6 and Observation 2.2(d), $\dim_{1,f}(G)=O(m^{2})$. To see
that $\dim_{1,f}(G)=\Omega(m^{2})$, suppose that the grid graph
$G=P_{4m}\times P_{3m}$ is drawn in the $xy$-plane with the four corners at
$(1,1)$, $(4m,1)$, $(1,3m)$ and $(4m,3m)$ with horizontal and vertical edges
of equal lengths, and let $g:V(G)\rightarrow[0,1]$ be any $1$-truncated
resolving function of $G$. Then, for every $P_{4}\times P_{3}$ subgraph, say
$B_{i,j}$, of $G$ with the four corners $(1+4i,1+3j)$, $(4+4i,1+3j)$,
$(1+4i,3+3j)$ and $(4+4i,3+3j)$, where $i,j\in\\{0,1,\ldots,m-1\\}$, we have
$R_{1}\\{(2+4i,2+3j),(3+4i,2+3j)\\}\subset V(B_{i,j})$, and thus
$g(V(B_{i,j}))\geq 1$. So,
$\dim_{1,f}(G)\geq\sum_{j=0}^{m-1}\sum_{i=0}^{m-1}g(V(B_{i,j}))\geq m^{2}$,
and hence $\dim_{1,f}(G)=\Omega(m^{2})$. Therefore,
$\dim_{1,f}(G)=\Theta(m^{2})$. ∎

######  Theorem 3.9.

For some positive integer $k>1$, let $G=P_{(2k+2)^{2}}\times P_{(2k+1)^{2}}$.
Then $\dim_{k,f}(G)=\Theta(k^{2})$, and thus both
$\frac{\dim_{1,f}(G)}{\dim_{k,f}(G)}$ and $\frac{\dim_{k,f}(G)}{\dim_{f}(G)}$
can be arbitrarily large.

###### Proof.

For some positive integer $k>1$, let $G=P_{(2k+2)^{2}}\times P_{(2k+1)^{2}}$.
Then $\dim_{f}(G)=2$ by Theorem 3.1(f), and $\dim_{1,f}(G)=\Theta(k^{4})$ by
Proposition 3.8. Next, we show that $\dim_{k,f}(G)=\Theta(k^{2})$. By
Proposition 3.7 and Observation 2.2(c), $\dim_{k,f}(G)=O(k^{2})$. To see that
$\dim_{k,f}(G)=\Omega(k^{2})$, notice that $G$ contains disjoint union of
$(2k+2)(2k+1)$ copies of $P_{2k+2}\times P_{2k+1}$. Let
$g:V(G)\rightarrow[0,1]$ be any $k$-truncated resolving function of $G$. For
each subgraph $P_{2k+2}\times P_{2k+1}$ of $G$, if $x$ and $y$ are the two
adjacent central vertices of $P_{2k+2}\times P_{2k+1}$, then
$R_{k}\\{x,y\\}\subseteq V(P_{2k+2}\times P_{2k+1})$, and hence
$g(V(P_{2k+2}\times P_{2k+1}))\geq g(R_{k}\\{x,y\\})\geq 1$; thus
$\dim_{k,f}(G)\geq(2k+2)(2k+1)$. So, $\dim_{k,f}(G)=\Omega(k^{2})$. Therefore,
$\dim_{k,f}(G)=\Theta(k^{2})$ for some positive integer $k>1$, and both
$\frac{\dim_{1,f}(G)}{\dim_{k,f}(G)}$ and $\frac{\dim_{k,f}(G)}{\dim_{f}(G)}$
can be arbitrarily large. ∎

Next, we characterize grid graphs $G$ satisfying $\dim_{1,f}(G)=\dim_{f}(G)$.

######  Proposition 3.10.

For the grid graph $G=P_{s}\times P_{t}$ with $s\geq t\geq 2$,
$\dim_{1,f}(G)=\dim_{f}(G)$ if and only if $G\in\\{P_{2}\times
P_{2},P_{3}\times P_{2},P_{4}\times P_{2},P_{3}\times P_{3}\\}$.

Figure 1: The four grid graphs $G$ with $\dim_{1,f}(G)=\dim_{f}(G)$.

###### Proof.

Let $G=P_{s}\times P_{t}$ with $s\geq t\geq 2$.

($\Leftarrow$) Let $G\in\\{P_{2}\times P_{2},P_{3}\times P_{2},P_{4}\times
P_{2},P_{3}\times P_{3}\\}$; see Figure 1. For each grid graph $G$ in Figure
1, if we let $g:V(G)\rightarrow[0,1]$ be a function defined by
$g(v)=\frac{1}{2}$ if $v$ is a solid vertex and $g(w)=0$ if $w$ is an open
vertex, then $g$ is a $1$-truncated resolving function of $G$. So,
$\dim_{1,f}(G)\leq g(V(G))=2$. Since $\dim_{1,f}(G)\geq\dim_{f}(G)=2$ by
Observation 2.2(d) and Theorem 3.1(f), $\dim_{1,f}(G)=\dim_{f}(G)=2$.

($\Rightarrow$) Let $\dim_{1,f}(G)=\dim_{f}(G)$. Let the grid graph $G$ be
drawn in the $xy$-plane with the four corners at $(1,1)$, $(s,1)$, $(1,t)$ and
$(s,t)$ with horizontal and vertical edges of equal lengths; we denote by
$u_{i,j}$ the vertex $(i,j)$. Let $g:V(G)\rightarrow[0,1]$ be any
$1$-truncated resolving function of $G$.

First, suppose $G=P_{s}\times P_{t}$ for $s,t\geq 4$. Then
$R_{1}\\{u_{1,1},u_{2,2}\\}=\\{u_{1,1},u_{2,2},u_{2,3},u_{3,2}\\}$,
$R_{1}\\{u_{1,2},u_{2,1}\\}=\\{u_{1,2},u_{1,3},u_{2,1},u_{3,1}\\}$ and
$R_{1}\\{u_{s-1,t},u_{s,t-1}\\}=\\{u_{s-2,t},u_{s-1,t},u_{s,t-1},u_{s,t-2}\\}$;
thus $g(u_{1,1})+g(u_{2,2})+g(u_{2,3})+g(u_{3,2})\geq 1$,
$g(u_{1,2})+g(u_{1,3})+g(u_{2,1})+g(u_{3,1})\geq 1$ and
$g(u_{s-2,t})+g(u_{s-1,t})+g(u_{s,t-1})+g(u_{s,t-2})\geq 1$. By summing over
the three inequalities, we have $g(V(G))\geq 3$ since $s,t\geq 4$; thus
$\dim_{1,f}(G)\geq 3>2=\dim_{f}(G)$. So, $\dim_{1,f}(G)=\dim_{f}(G)$ implies
$t\leq 3$.

Second, suppose $G=P_{s}\times P_{3}$ for $s\geq 3$. If $s=3$, then
$\dim_{1,f}(G)=2=\dim_{f}(G)$ as shown above. If $s=4$, then
$R_{1}\\{u_{1,1},u_{2,2}\\}=\\{u_{1,1},u_{2,2},u_{2,3},u_{3,2}\\}$,
$R_{1}\\{u_{1,2},u_{2,1}\\}=\\{u_{1,2},u_{1,3},u_{2,1},u_{3,1}\\}$,
$R_{1}\\{u_{3,3},u_{4,2}\\}=\\{u_{2,3},u_{3,3},u_{4,2},u_{4,1}\\}$,
$R_{1}\\{u_{3,2},u_{4,3}\\}=\\{u_{2,2},u_{3,1},u_{3,2},u_{4,3}\\}$ and
$R_{1}\\{u_{1,1},u_{4,3}\\}=\\{u_{1,1},u_{1,2},u_{2,1},u_{3,3},u_{4,2},u_{4,3}\\}$;
thus, $g(u_{1,1})+g(u_{2,2})+g(u_{2,3})+g(u_{3,2})\geq 1$,
$g(u_{1,2})+g(u_{1,3})+g(u_{2,1})+g(u_{3,1})\geq 1$,
$g(u_{2,3})+g(u_{3,3})+g(u_{4,2})+g(u_{4,1})\geq 1$,
$g(u_{2,2})+g(u_{3,1})+g(u_{3,2})+g(u_{4,3})\geq 1$ and
$g(u_{1,1})+g(u_{1,2})+g(u_{2,1})+g(u_{3,3})+g(u_{4,2})+g(u_{4,3})\geq 1$. By
summing over the five inequalities, we have $2g(V(G))\geq 5$, and hence
$\dim_{1,f}(G)\geq\frac{5}{2}>2=\dim_{f}(G)$. If $s\geq 5$, then
$R_{1}\\{u_{1,1},u_{2,2}\\}=\\{u_{1,1},u_{2,2},u_{2,3},u_{3,2}\\}$,
$R_{1}\\{u_{1,2},u_{2,1}\\}=\\{u_{1,2},u_{1,3},u_{2,1},u_{3,1}\\}$ and
$R_{1}\\{u_{s-1,3},u_{s,2}\\}=\\{u_{s-2,3},u_{s-1,3},u_{s,2},u_{s,1}\\}$;
thus, $g(u_{1,1})+g(u_{2,2})+g(u_{2,3})+g(u_{3,2})\geq 1$,
$g(u_{1,2})+g(u_{1,3})+g(u_{2,1})+g(u_{3,1})\geq 1$ and
$g(u_{s-2,3})+g(u_{s-1,3})+g(u_{s,2})+g(u_{s,1})\geq 1$. By summing over the
three inequalities, we have $g(V(G))\geq 3$ since $s\geq 5$, and hence
$\dim_{1,f}(G)\geq 3>2=\dim_{f}(G)$.

Third, suppose $G=P_{s}\times P_{2}$ for $s\geq 2$. If $s\in\\{2,3,4\\}$, then
$\dim_{1,f}(G)=2=\dim_{f}(G)$ as shown above. So, suppose $s\geq 5$. Then
$R_{1}\\{u_{1,1},u_{2,2}\\}=\\{u_{1,1},u_{2,2},u_{3,2}\\}$,
$R_{1}\\{u_{1,2},u_{2,1}\\}=\\{u_{1,2},u_{2,1},u_{3,1}\\}$ and
$R_{1}\\{u_{s,1},u_{s,2}\\}=\\{u_{s-1,1},u_{s-1,2},u_{s,1},u_{s,2}\\}$; thus,
$g(u_{1,1})+g(u_{2,2})+g(u_{3,2})\geq 1$,
$g(u_{1,2})+g(u_{2,1})+g(u_{3,1})\geq 1$ and
$g(u_{s-1,1})+g(u_{s-1,2})+g(u_{s,1})+g(u_{s,2})\geq 1$. By summing over the
three inequalities, we have $g(V(G))\geq 3$ since $s\geq 5$, and thus
$\dim_{1,f}(G)\geq 3>2=\dim_{f}(G)$. ∎

###  3.4 Trees

We examine $\dim_{k,f}(T)$ for non-trivial trees $T$. For $n\geq 2$,
$\dim_{k,f}(P_{n})=\dim_{f}(P_{n})$ if and only if $n\in\\{2,3,\ldots,k+2\\}$
by Theorems 2.4(c) and 2.7. We characterize trees $T$ satisfying
$\dim_{1,f}(T)=\dim_{f}(T)$. For trees $T$ with $ex(T)=1$ and for any
$k\in\mathbb{Z}^{+}$, we also characterize $T$ satisfying
$\dim_{k,f}(T)=\dim_{f}(T)$.

We first consider $\dim_{k,f}(P_{n})$.

######  Theorem 3.11.

Let $k\in\mathbb{Z}^{+}$ and $n\geq 2$.

  * (a)

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

  * (b)

If $k+3\leq n\leq 2k+3$, then $\dim_{k,f}(P_{n})=\frac{6+2k-n}{5+2k-n}$.

  * (c)

Let $n\geq 2k+4$.

    * (i)

If $n\equiv 1\pmod{(2k+2)}$, then $\dim_{k,f}(P_{n})=\frac{n+k}{2k+2}$.

    * (ii)

If $n\equiv 2,3,\ldots,k+2\pmod{(2k+2)}$, then
$\dim_{k,f}(P_{n})=\lceil\frac{n}{2k+2}\rceil$.

    * (iii)

If $n\equiv 0\pmod{(2k+2)}$ or $n\equiv k+3,k+4,\ldots,2k+1\pmod{(2k+2)}$,
then
$\lceil\frac{n}{2k+2}\rceil\leq\dim_{k,f}(P_{n})\leq\lceil\frac{n}{2k+2}\rceil+\frac{1}{2}$.

###### Proof.

Let $k\in\mathbb{Z}^{+}$. For $n\geq 2$, let $P_{n}$ be given by
$u_{1},u_{2},\ldots,u_{n}$. Let $g:V(P_{n})\rightarrow[0,1]$ be any
$k$-truncated resolving function of $P_{n}$. For (a), suppose $n\leq k+2$.
Then $\dim_{k,f}(P_{n})=1$ by Theorem 2.7.

For (b), suppose $k+3\leq n\leq 2k+3$. Then
$R_{k}\\{u_{1},u_{2}\\}=\cup_{i=1}^{k+2}\\{u_{i}\\}$,
$R_{k}\\{u_{n-1},u_{n}\\}=\cup_{i=n-(k+1)}^{n}\\{u_{i}\\}$, and
$R_{k}\\{u_{i-1},u_{i+1}\\}=V(P_{n})-\\{u_{i}\\}$ for $u_{i}\in
R_{k}\\{u_{1},u_{2}\\}\cap R_{k}\\{u_{n-1},u_{n}\\}$ (i.e., $n-k-1\leq i\leq
k+2$). By summing over the $(6+2k-n)$ inequalities, we have
$(5+2k-n)g(V(P_{n}))\geq 6+2k-n$, i.e.,
$g(V(P_{n}))\geq\frac{6+2k-n}{5+2k-n}$; thus,
$\dim_{k,f}(P_{n})\geq\frac{6+2k-n}{5+2k-n}$. On the other hand, let
$h:V(P_{n})\rightarrow[0,1]$ be a function defined by

$h(u_{i})=\left\\{\begin{array}[]{ll}\frac{1}{5+2k-n}&\mbox{ if
}u_{i}\in\\{u_{1},u_{n}\\}\cup(R_{k}\\{u_{1},u_{2}\\}\cap
R_{k}\\{u_{n-1},u_{n}\\}),\\\ 0&\mbox{ otherwise}.\\\ \end{array}\right.$

Then $h$ is a $k$-truncated resolving function of $P_{n}$ with
$h(V(P_{n}))=\frac{6+2k-n}{5+2k-n}$; thus,
$\dim_{k,f}(P_{n})\leq\frac{6+2k-n}{5+2k-n}$. Therefore,
$\dim_{k,f}(P_{n})=\frac{6+2k-n}{5+2k-n}$ for $k+3\leq n\leq 2k+3$.

For (c), let $n\geq 2k+4$, and we consider three cases.

Case 1: $n\equiv 1\pmod{(2k+2)}$. Note that
$R_{k}\\{u_{1},u_{2}\\}=\cup_{i=1}^{k+2}\\{u_{i}\\}$,
$R_{k}\\{u_{n-1},u_{n}\\}=\cup_{i=n-(k+1)}^{n}\\{u_{i}\\}$, and
$R_{k}\\{u_{i-1},u_{i+1}\\}=\cup_{j=1}^{k+1}\\{u_{i-j},u_{i+j}\\}$ for
$i\equiv 1\pmod{(k+1)}$ and $i\not\in\\{1,n\\}$. By summing over the
$\lceil\frac{n}{k+1}\rceil$ inequalities, we have
$2g(V(P_{n}))\geq\lceil\frac{n}{k+1}\rceil=\frac{n-1}{k+1}+1=\frac{n+k}{k+1}$,
i.e., $g(V(P_{n}))\geq\frac{n+k}{2(k+1)}$; thus,
$\dim_{k,f}(P_{n})\geq\frac{n+k}{2k+2}$. On the other hand, if we let
$h:V(P_{n})\rightarrow[0,1]$ be a function defined by

$h(u_{i})=\left\\{\begin{array}[]{ll}\frac{1}{2}&\mbox{ if }i\equiv
1\pmod{(k+1)},\\\ 0&\mbox{ otherwise},\\\ \end{array}\right.$

then $h$ is a $k$-truncated resolving function of $P_{n}$ with
$h(V(P_{n}))=\frac{1}{2}\lceil\frac{n}{k+1}\rceil=\frac{n+k}{2k+2}$; thus,
$\dim_{k,f}(P_{n})\leq\frac{n+k}{2k+2}$. Therefore,
$\dim_{k,f}(P_{n})=\frac{n+k}{2k+2}$ for $n\equiv 1\pmod{(2k+2)}$.

Case 2: $n\equiv 2,3,\ldots,k+2\pmod{(2k+2)}$. Note that
$R_{k}\\{u_{1},u_{2}\\}=\cup_{i=1}^{k+2}\\{u_{i}\\}$,
$R_{k}\\{u_{n-1},u_{n}\\}=\cup_{i=n-(k+1)}^{n}\\{u_{i}\\}$, and
$R_{k}\\{u_{(2k+2)i+1},u_{(2k+2)i+2}\\}=\cup_{j=1-k}^{k+2}\\{u_{(2k+2)i+j}\\}$
for $i\in\\{1,2,\ldots,\lceil\frac{n}{2k+2}\rceil-2\\}$. By summing over the
$\lceil\frac{n}{2k+2}\rceil$ inequalities, we have
$g(V(P_{n}))\geq\lceil\frac{n}{2k+2}\rceil$; thus,
$\dim_{k,f}(P_{n})\geq\lceil\frac{n}{2k+2}\rceil$. On the other hand, let
$h:V(P_{n})\rightarrow[0,1]$ be a function defined by

$h(u_{i})=\left\\{\begin{array}[]{ll}\frac{1}{2}&\mbox{ if }i\equiv
1\pmod{(k+1)}\mbox{ and }1\leq i\leq\frac{n}{2},\mbox{ or }n+1-i\equiv
1\pmod{(k+1)}\mbox{ and }\frac{n}{2}<i\leq n,\\\ 0&\mbox{ otherwise}.\\\
\end{array}\right.$

Then $h$ is a $k$-truncated resolving function of $P_{n}$ with
$h(V(P_{n}))=\lceil\frac{n}{2k+2}\rceil$; thus,
$\dim_{k,f}(P_{n})\leq\lceil\frac{n}{2k+2}\rceil$. Therefore,
$\dim_{k,f}(P_{n})=\lceil\frac{n}{2k+2}\rceil$ for $n\equiv
2,3,\ldots,k+2\pmod{(2k+2)}$.

Case 3: $n\equiv 0\pmod{(2k+2)}$ or $n\equiv k+3,\ldots,2k+1\pmod{(2k+2)}$.
Note that
$R_{k}\\{u_{(2k+2)i+k+1},u_{(2k+2)i+k+2}\\}=\cup_{j=1}^{2k+2}\\{u_{(2k+2)i+j}\\}$
for each $i\in\\{0,1,\ldots,\lceil\frac{n}{2k+2}\rceil-2\\}$ and
$R_{k}\\{u_{n-1},u_{n}\\}=\cup_{i=n-(k+1)}^{n}\\{u_{i}\\}$. By summing over
the $\lceil\frac{n}{2k+2}\rceil$ inequalities, we have
$g(V(P_{n}))\geq\lceil\frac{n}{2k+2}\rceil$; thus,
$\dim_{k,f}(P_{n})\geq\lceil\frac{n}{2k+2}\rceil$. If
$h:V(P_{n})\rightarrow[0,1]$ is a function defined by

$h(u_{i})=\left\\{\begin{array}[]{ll}\frac{1}{2}&\mbox{ if
}i=\lceil\frac{n}{2}\rceil,\mbox{ or}\\\ {}&\ \ \ 1\leq
i<\lceil\frac{n}{2}\rceil\mbox{ and }i\equiv 1\\!\\!\\!\pmod{(k+1)},\mbox{ or
}\\\ {}&\ \ \ \lceil\frac{n}{2}\rceil<i\leq n\mbox{ and }n+1-i\equiv
1\\!\\!\\!\pmod{(k+1)},\\\ 0&\mbox{ otherwise},\\\ \end{array}\right.$

then $h$ is a $k$-truncated resolving function of $P_{n}$ with
$h(V(P_{n}))=\lceil\frac{n}{2k+2}\rceil+\frac{1}{2}$; thus,
$\dim_{k,f}(P_{n})\leq\lceil\frac{n}{2k+2}\rceil+\frac{1}{2}$. Therefore,
$\lceil\frac{n}{2k+2}\rceil\leq\dim_{k,f}(P_{n})=\lceil\frac{n}{2k+2}\rceil+\frac{1}{2}$
for $n\equiv 0\pmod{(2k+2)}$ or $n\equiv k+3,\ldots,2k+1\pmod{(2k+2)}$. ∎

Theorem 3.11 implies the following.

######  Corollary 3.12.

Let $n\geq 2$.

  * (a)

If $n\in\\{2,3\\}$, then $\dim_{1,f}(P_{n})=1$; if $n\in\\{4,5\\}$, then
$\dim_{1,f}(P_{n})=\frac{8-n}{7-n}$.

  * (b)

If $n\geq 6$, then

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

  * (c)

If $n\geq 8$ and $n\equiv 0\pmod{4}$, then
$\frac{n}{4}\leq\dim_{1,f}(P_{n})\leq\frac{n+2}{4}$.

Next, we characterize non-trivial trees $T$ satisfying
$\dim_{1,f}(T)=\dim_{f}(T)$. We recall some terminology and notation. An
_exterior degree-two vertex_ is a vertex of degree $2$ that lies on a path
from a terminal vertex to its major vertex, and an _interior degree-two
vertex_ is a vertex of degree $2$ such that the shortest path to any terminal
vertex includes a major vertex. For $v\in M(T)$, let $T_{v}$ be the subtree of
$T$ induced by $v$ and all vertices belonging to the paths joining $v$ with
its terminal vertices. We begin with the following useful lemmas.

######  Lemma 3.13.

Let $T$ be a tree with $ex(T)\geq 1$, and let $g:V(T)\rightarrow[0,1]$ be any
minimum resolving function of $T$. Then, for each $v\in M_{2}(T)$ with
$ter(v)=\alpha\geq 2$, $g(V(T_{v})-\\{v\\})=\frac{\alpha}{2}$ and $\sum_{v\in
M_{2}(T)}(g(V(T_{v}))-g(v))=\dim_{f}(T)$.

###### Proof.

Let $T$ be a tree with $ex(T)\geq 1$, and let $g:V(T)\rightarrow[0,1]$ be any
minimum resolving function of $T$. Let
$M_{2}(T)=\\{v_{1},v_{2},\ldots,v_{a}\\}$, where $a\geq 1$. For each
$i\in\\{1,2\ldots,a\\}$, let $ter(v_{i})=\sigma_{i}\geq 2$, let
$\ell_{i,1},\ell_{i,2},\ldots,\ell_{i,\sigma_{i}}$ be the terminal vertices of
$v_{i}$, and let $N(v_{i})=\\{s_{i,1},s_{i,2},\ldots,s_{i,\sigma_{i}}\\}$ such
that $s_{i,j}$ lies on the $v_{i}-\ell_{i,j}$ path and we denote by $P^{i,j}$
the $s_{i,j}-\ell_{i,j}$ path, where $j\in\\{1,2,\ldots,\sigma_{i}\\}$.

For each $i\in\\{1,2,\ldots,a\\}$ and for any distinct
$x,y\in\\{1,2,\ldots,\sigma_{i}\\}$, note that
$R\\{s_{i,x},s_{i,y}\\}=V(P^{i,x})\cup V(P^{i,y})$, and thus
$g(V(P^{i,x}))+g(V(P^{i,y}))\geq 1$; by summing over the $\sigma_{i}\choose 2$
inequalities, we have
$(\sigma_{i}-1)\sum_{j=1}^{\sigma_{i}}g(V(P^{i,j}))\geq{\sigma_{i}\choose 2}$,
which implies
$g(V(T_{v_{i}}))-g(v_{i})=\sum_{j=1}^{\sigma_{i}}g(V(P^{i,j}))\geq\frac{\sigma_{i}}{2}$.
So,
$\sum_{i=1}^{a}(g(V(T_{v_{i}}))-g(v_{i}))\geq\sum_{i=1}^{a}\frac{\sigma_{i}}{2}=\frac{1}{2}(\sigma(T)-ex_{1}(T))=\dim_{f}(T)$.
Since $g$ is a minimum resolving function of $T$, $g(V(T))=\dim_{f}(T)$; thus,
$g(V(T_{v_{i}}))-g(v_{i})=\frac{\sigma_{i}}{2}$ for each
$i\in\\{1,2,\ldots,a\\}$ and
$\sum_{i=1}^{a}(g(V(T_{v_{i}}))-g(v_{i}))=\dim_{f}(T)$. ∎

Lemma 3.13 implies the following

######  Corollary 3.14.

Let $T$ be a tree with $ex(T)\geq 1$, and let $g:V(T)\rightarrow[0,1]$ be any
minimum resolving function of $T$. If $x$ is a major vertex, an interior
degree-two vertex, or a vertex belonging to $T_{v}$ for $v\in M_{1}(T)$, then
$g(x)=0$.

######  Lemma 3.15.

Let $T$ be a tree with $ex(T)\geq 1$ satisfying $\dim_{1,f}(T)=\dim_{f}(T)$.

  * (a)

If $v\in M_{2}(T)$, then every terminal vertex of $v$ is adjacent to $v$ in
$T$.

  * (b)

$T$ contains no major vertex of terminal degree one.

  * (c)

$T$ contains neither a major vertex of terminal degree zero nor an interior
degree-two vertex.

###### Proof.

Let $T$ be a tree with $ex(T)\geq 1$ satisfying $\dim_{1,f}(T)=\dim_{f}(T)$.
Let $g:V(T)\rightarrow[0,1]$ be any minimum resolving function of $T$, and let
$h:V(T)\rightarrow[0,1]$ be any minimum $1$-truncated resolving function of
$T$.

(a) Let $v\in M_{2}(T)$ with $ter(v)=\alpha\geq 2$. Let
$\ell_{1},\ell_{2},\ldots,\ell_{\alpha}$ be the terminal vertices of $v$ in
$T$. Suppose $d(v,\ell_{i})\geq 2$ for some $i\in\\{1,2,\ldots,\alpha\\}$. By
relabeling the vertices of $T$ if necessary, let $d(v,\ell_{1})\geq 2$.

First, let $\alpha\geq 3$. Let the $v-\ell_{1}$ path be given by
$v=s_{0},s_{1},\ldots,s_{d}=\ell_{1}$, where $d\geq 2$, and we denote by $P$
the $v-\ell_{1}$ path in $T$. Since
$R_{1}\\{s_{d-1},s_{d}\\}=\\{s_{d-2},s_{d-1},s_{d}\\}\subseteq V(P)$,
$h(V(P))\geq 1$. Since $\dim_{1,f}(T)=\dim_{f}(T)$ and $\alpha\geq 3$,
$h(V(T_{v}))-h(V(P))\geq\frac{\alpha-1}{2}$ using the argument in the proof
for Lemma 3.13. So,
$h(V(T_{v}))\geq\frac{\alpha+1}{2}>\frac{\alpha}{2}=g(V(T_{v}))$. By Lemma
3.13 and Corollary 3.14, $\dim_{1,f}(T)>\dim_{f}(T)$. So,
$\dim_{1,f}(T)=\dim_{f}(T)$ implies that $d(v,\ell_{i})=1$ for each
$i\in\\{1,2,\ldots,\alpha\\}$.

Second, let $\alpha=2$. Let the $v-\ell_{1}$ path and the $v-\ell_{2}$ path,
respectively, be given by $v=s_{0},s_{1},\ldots,s_{d}=\ell_{1}$ and
$v=s_{0},s^{\prime}_{1},\ldots,s^{\prime}_{t}=\ell_{2}$, where $d\geq 2$; let
$P^{1}$ and $P^{2}$ denote the $s_{1}-\ell_{1}$ path and the
$s^{\prime}_{1}-\ell_{2}$ path, respectively. Note that
$R_{1}\\{s_{d-1},s_{d}\\}\subseteq\\{v\\}\cup V(P^{1})$,
$R_{1}\\{s_{1},s^{\prime}_{1}\\}\subseteq V(P^{1})\cup V(P^{2})$,
$R_{1}\\{v,s_{2}\\}\subseteq(N[v]\cup V(P^{1}))-\\{s_{1}\\}$ and
$R_{1}\\{v,s^{\prime}_{1}\\}\subseteq N[v]\cup V(P^{2})$. So,
$h(v)+h(V(P^{1}))\geq 1$, $h(V(P^{1}))+h(V(P^{2}))\geq 1$, $h(N[v]\cup
V(P^{1}))-h(s_{1})\geq 1$ and $h(N[v]\cup V(P^{2}))\geq 1$. Since each vertex
in $N[v]\cup V(T_{v})$ appears at most $3$ times in the $4$ inequalities, by
summing over the $4$ inequalities, we have $3h(N[v]\cup V(T_{v}))\geq 4$.
Since each vertex in $N[v]-\\{s_{1},s^{\prime}_{1}\\}$ is either a major
vertex or an interior degree-two vertex in $T$,
$g(N[v]-\\{s_{1},s^{\prime}_{1}\\})=0$ by Corollary 3.14. So, $h(N[v]\cup
V(T_{v}))\geq\frac{4}{3}>1=g(N[v]\cup V(T_{v}))=g(V(T_{v})-\\{v\\})$. Thus,
$\dim_{1,f}(T)=\dim_{f}(T)$ implies that $d(v,\ell_{1})=1=d(v,\ell_{2})$.

(b) Let $v\in M_{1}(T)$, and let $\ell$ be the terminal vertex of $v$ in $T$
such that the $v-\ell$ path is given by $v=s_{0},s_{1},\ldots,s_{d}=\ell$. If
$d(v,\ell)\geq 2$, then $R_{1}\\{s_{d-1},s_{d}\\}\subseteq V(T_{v})$ and
$h(V(T_{v}))\geq 1>0=g(V(T_{v}))$ by Corollary 3.14. If $d(v,\ell)=1$, then
$R_{1}\\{v,\ell\\}=N[v]$ and $h(N[v])\geq 1>0=g(N[v])$ since each vertex in
$N[v]$ is a major vertex, an interior degree-two vertex, or a vertex belonging
to $T_{v}$ for $v\in M_{1}(T)$. So, $\dim_{1,f}(T)=\dim_{f}(T)$ implies that
$M_{1}(T)=\emptyset$.

(c) Suppose $x$ is either an interior degree-two vertex or a major vertex of
terminal degree zero in $T$. Then there exist distinct $w,w^{\prime}\in
M_{2}(T)$ such that $x$ lies on the $w-w^{\prime}$ path and that $w$ and
$w^{\prime}$ are the only exterior major vertices on the $w-w^{\prime}$ path.
By relabeling the vertices of $T$ if necessary, we may assume that $xw\in
E(T)$. If $\ell_{1},\ell_{2},\ldots,\ell_{\alpha}$ are the terminal vertices
of $w$, where $\alpha\geq 2$, then $\ell_{i}w\in E(T)$ for each
$i\in\\{1,2,\ldots,\alpha\\}$ by (a) of the current lemma.

For each $i\in\\{1,2,\ldots,\alpha\\}$,
$R_{1}\\{\ell_{i},x\\}=\\{\ell_{i}\\}\cup(N[x]-\\{w\\})$ and
$h(\ell_{i})+h(N[x]-\\{w\\})\geq 1$. By summing over the $\alpha$
inequalities, we have $(\sum_{i=1}^{\alpha}h(\ell_{i}))+\alpha
h(N[x]-\\{w\\})\geq\alpha$. Since each vertex in $N[x]-\\{w\\}$ is either a
major vertex or an interior degree-two vertex in $T$, $g(N[x]-\\{w\\})=0$ by
Corollary 3.14. So, we have $(\sum_{i=1}^{\alpha}h(\ell_{i}))+\alpha
h(N[x]-\\{w\\})\geq\alpha>\frac{\alpha}{2}=(\sum_{i=1}^{\alpha}g(\ell_{i}))+\alpha
g(N[x]-\\{w\\})=g(V(T_{w})-\\{w\\})$. So, $\dim_{1,f}(T)=\dim_{f}(T)$ implies
that $T$ contains neither a major vertex of terminal degree zero nor an
interior degree-two vertex. ∎

######  Proposition 3.16.

Let $T$ be a non-trivial tree. Then $\dim_{1,f}(T)=\dim_{f}(T)$ if and only if
$T\in\\{P_{2},P_{3}\\}$, or $ex(T)\geq 1$ and $V(T)=M_{2}(T)\cup L(T)$.

###### Proof.

Let $T$ be a tree of order $n\geq 2$.

($\Leftarrow$) If $T\in\\{P_{2},P_{3}\\}$, then $\dim_{1,f}(T)=1=\dim_{f}(T)$
by Theorems 2.4(c) and 2.7. Now, suppose $ex(T)\geq 1$ and $V(T)=M_{2}(T)\cup
L(T)$. If $g:V(T)\rightarrow[0,1]$ is a function defined by $g(u)=\frac{1}{2}$
for each $u\in L(T)$ and $g(w)=0$ for each $w\in M_{2}(T)$, then $g$ is a
$1$-truncated resolving function of $T$ with $g(V(T))=\frac{1}{2}\sigma(T)$;
thus $\dim_{1,f}(T)\leq\frac{1}{2}\sigma(T)$. Since
$\dim_{1,f}(T)\geq\dim_{f}(T)=\frac{1}{2}\sigma(T)$ by Observation 2.2(d) and
Theorem 3.1(a), $\dim_{1,f}(T)=\frac{1}{2}\sigma(T)=\dim_{f}(T)$.

($\Rightarrow$) Let $\dim_{1,f}(T)=\dim_{f}(T)$. If $ex(T)=0$, then $T=P_{n}$
and $\dim_{f}(P_{n})=1$ by Theorem 2.4(c). So,
$\dim_{1,f}(P_{n})=\dim_{f}(P_{n})$ implies $\dim_{1,f}(P_{n})=1$, and thus
$n\in\\{2,3\\}$ by Theorem 2.7.

Now, suppose $ex(T)\geq 1$. By Lemma 3.15(b)(c), $T$ contains neither an
interior degree-two vertex nor a major vertex with terminal degree at most
one. Moreover, by Lemma 3.15(a), $T$ contains no exterior degree-two vertex.
So, each vertex in $T$ is either a major vertex with terminal degree at least
two, or a leaf that is adjacent to some exterior major vertex in $T$. ∎

For any $k\in\mathbb{Z}^{+}$, it’s an interesting yet a challenging task to
characterize all connected graphs $G$ satisfying $\dim_{k}(G)=\dim(G)$ or
$\dim_{k,f}(G)=\dim_{f}(G)$ even when $G$ is restricted to trees. We recall
the following result on trees $T$ satisfying $\dim_{1}(T)=\dim(T)$.

######  Proposition 3.17.

_[13]_ For any non-trivial tree $T$, $\dim_{1}(T)=\dim(T)$ if and only if
$T\in\\{P_{2},P_{3}\\}$ or $T$ is a tree obtained from the star $K_{1,x}$
($x\geq 3$) by subdividing at most $x-1$ edges exactly once.

Now, for trees $T$ with $ex(T)=1$, we characterize $T$ satisfying
$\dim_{k,f}(T)=\dim_{f}(T)$.

######  Proposition 3.18.

Let $k\in\mathbb{Z}^{+}$, and let $T$ be a tree with $ex(T)=1$ such that
$\ell_{1},\ell_{2},\ldots,\ell_{\alpha}$ are the terminal vertices of the
exterior major vertex $v$ in $T$. Then $\dim_{k,f}(T)=\dim_{f}(T)$ if and only
if $d(v,\ell_{i})\leq k$ for each $i\in\\{1,2,\ldots,\alpha\\}$.

###### Proof.

Let $k\in\mathbb{Z}^{+}$, and let $T$ be a tree with $ex(T)=1$. Let $v$ be the
exterior major vertex of $T$, $N(v)=\\{s_{1},s_{2},\ldots,s_{\alpha}\\}$, and
let $\ell_{1},\ell_{2},\ldots,\ell_{\alpha}$ be the terminal vertices of $v$
in $T$ such that $s_{i}$ lies on the $v-\ell_{i}$ path for each
$i\in\\{1,2,\ldots,\alpha\\}$, where $\alpha\geq 3$. Let $P^{i}$ denote the
$s_{i}-\ell_{i}$ path, where $i\in\\{1,2,\ldots,\alpha\\}$.

($\Leftarrow$) Suppose $d(v,\ell_{i})\leq k$ for each
$i\in\\{1,2,\ldots,\alpha\\}$. Let $g:V(T)\rightarrow[0,1]$ be a function
defined by

$g(u)=\left\\{\begin{array}[]{ll}\frac{1}{2}&\mbox{ if
}u\in\\{s_{1},s_{2},\ldots,s_{\alpha}\\},\\\ 0&\mbox{
otherwise}.\end{array}\right.$

We show that $g$ is a $k$-truncated resolving function for $T$. Let $x$ and
$y$ be distinct vertices in $T$. First, suppose $x$ and $y$ lie on the
$v-\ell_{i}$ path for some $i\in\\{1,2,\ldots,\alpha\\}$; let $d(v,x)<d(v,y)$
without loss of generality. Since $d(x,s_{j})\leq k$ and $d_{k}(x,s_{j})\neq
d_{k}(y,s_{j})$ for each $j\in\\{1,2,\ldots,\alpha\\}-\\{i\\}$,
$R_{k}\\{x,y\\}\supseteq N(v)-\\{s_{i}\\}$ and $g(R_{k}\\{x,y\\})\geq
g(N(v))-g(s_{i})=\frac{\alpha-1}{2}\geq 1$ since $\alpha\geq 3$. Second,
suppose $x$ lies on the $s_{i}-\ell_{i}$ path and $y$ lies on the
$s_{j}-\ell_{j}$ path for distinct $i,j\in\\{1,2,\ldots,\alpha\\}$. If
$d(v,x)=d(v,y)$, then $R_{k}\\{x,y\\}=V(P^{i})\cup V(P^{j})$ and
$g(R_{k}\\{x,y\\})\geq g(V(P^{i}))+g(V(P^{j}))\geq g(s_{i})+g(s_{j})=1$. If
$d(v,x)\neq d(v,y)$, say $d(v,x)<d(v,y)$, then $d(x,s_{t})\leq k$ and
$d_{k}(x,s_{t})\neq d_{k}(y,s_{t})$ for each
$t\in\\{1,2,\ldots,\alpha\\}-\\{j\\}$; thus, $R_{k}\\{x,y\\}\supseteq
N(v)-\\{s_{j}\\}$ and $g(R_{k}\\{x,y\\})\geq
g(N(v))-g(s_{j})\geq\frac{\alpha-1}{2}\geq 1$. So, $g$ is a $k$-truncated
resolving function of $T$ with $g(V(T))=\frac{\alpha}{2}$, and thus
$\dim_{k,f}(T)\leq\frac{\alpha}{2}=\dim_{f}(T)$ by Theorem 3.1(a). Since
$\dim_{k,f}(T)\geq\dim_{f}(T)$ by Observation 2.2(c), we have
$\dim_{k,f}(T)=\frac{\alpha}{2}=\dim_{f}(T)$.

($\Rightarrow$) Let $\dim_{k,f}(T)=\dim_{f}(T)$. Assume, to the contrary, that
$d(v,\ell_{i})\geq k+1$ for some $i\in\\{1,2,\ldots,\alpha\\}$. By relabeling
the vertices of $T$ if necessary, let $d(v,\ell_{1})\geq k+1$ and let
$v-\ell_{1}$ path be given by
$v=u_{0},s_{1}=u_{1},u_{2},\ldots,u_{k},u_{k+1},\ldots,u_{z}=\ell_{1}$. Let
$h:V(T)\rightarrow[0,1]$ be a minimum $k$-truncated resolving function of $T$.
Since $R_{k}\\{u_{z-1},u_{z}\\}\subseteq\\{v\\}\cup V(P^{1})$,
$h(v)+h(V(P^{1}))\geq h(R_{k}\\{u_{z-1},u_{z}\\})\geq 1$. Note that, for any
distinct $i,j\in\\{2,3,\ldots,\alpha\\}$, $R_{k}\\{s_{i},s_{j}\\}\subseteq
V(P^{i})\cup V(P^{j})$ and $h(V(P^{i}))+h(V(P^{j}))\geq 1$; thus,
$\sum_{i=2}^{\alpha}h(V(P^{i}))\geq\frac{\alpha-1}{2}$. So,
$\dim_{k,f}(T)=h(V(T))=h(v)+\sum_{i=1}^{\alpha}h(V(P^{i}))\geq
1+\frac{\alpha-1}{2}=\frac{\alpha+1}{2}>\frac{\alpha}{2}=\dim_{f}(T)$, which
contradicts the assumption that $\dim_{k,f}(T)=\dim_{f}(T)$. So,
$d(v,\ell_{i})\leq k$ for each $i\in\\{1,2,\ldots,\alpha\\}$. ∎

##  4 Comparison on $\dim(G)$, $\dim_{f}(G)$, $\dim_{k}(G)$ and
$\dim_{k,f}(G)$

In this section, we examine the relation among $\dim_{f}(G)$, $\dim_{k,f}(G)$,
$\dim(G)$ and $\dim_{k}(G)$ for $k\in\mathbb{Z}^{+}$ in conjunction with
Observation 2.2. We show that, for two connected graphs $H$ and $G$ with
$H\subset G$, $\frac{\dim_{k,f}(H)}{\dim_{k,f}(G)}$ can be arbitrarily large.
We also show the existence of non-isomorphic graphs $G$ and $H$ with
$\dim_{k}(G)=\dim_{k}(H)$ and $\dim_{k,f}(G)\neq\dim_{k,f}(H)$. We conclude
the paper with some open problems.

It is known that metric dimension is not a monotone parameter on subgraph
inclusion (see [6]), and the following results were obtained in [13, 11].

######  Theorem 4.1.

Let $H$ and $G$ be connected graphs with $H\subset G$. Then

  * (a)

_[13]_ $\frac{\dim(H)}{\dim(G)}$ and $\frac{\dim_{1}(H)}{\dim_{1}(G)}$ can be
arbitrarily large;

  * (b)

_[11]_ for any $k\in\mathbb{Z}^{+}$, $\frac{\dim_{k}(H)}{\dim_{k}(G)}$ can be
arbitrarily large.

We recall the following construction from [13]. 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}\\})$; notice $H\subset G$. Since
$\textnormal{diam}(H)=1$ and $\textnormal{diam}(G)=2$, by Observation 2.3(b),
$\dim_{k,f}(H)=\dim_{f}(H)$ and $\dim_{k,f}(G)=\dim_{f}(G)$ for any
$k\in\mathbb{Z}^{+}$. Note that $\dim_{f}(H)=\frac{m(m+1)}{4}$ by Theorem
3.1(e), and $\dim_{f}(G)\leq m$ by Observation 2.2(a) since
$\\{u_{1},u_{2},\ldots,u_{m}\\}$ forms a resolving set of $G$. So,
$\frac{\dim_{k,f}(H)}{\dim_{k,f}(G)}=\frac{\dim_{f}(H)}{\dim_{f}(G)}\geq\frac{m+1}{4}$
for any $k\in\mathbb{Z}^{+}$, which implies the following

######  Corollary 4.2.

For any $k\in\mathbb{Z}^{+}$, there exist connected graphs $H$ and $G$ such
that $H\subset G$ and both $\frac{\dim_{f}(H)}{\dim_{f}(G)}$ and
$\frac{\dim_{k,f}(H)}{\dim_{k,f}(G)}$ can be arbitrarily large.

It was shown that $\frac{\dim_{k}(G)}{\dim(G)}$ and
$\frac{\dim_{k,f}(G)}{\dim_{f}(G)}$ can be arbitrarily large (see [11] and
Theorem 3.9, respectively). In view of Observation 2.2, it is easy to see that
$\dim(G)-\dim_{f}(G)$ and $\dim_{k}(G)-\dim_{k,f}(G)$ can be arbitrarily
large. We also show that $\dim(G)-\dim_{k,f}(G)$ and $\dim_{k,f}(G)-\dim(G)$
can be arbitrarily large.

######  Theorem 4.3.

_[4, 19, 20]_ For any tree $T$ that is not a path, $\dim(T)=\sigma(T)-ex(T)$.

######  Remark 4.4.

Let $k\in\mathbb{Z}^{+}$, and let $G$ be a non-trivial connected graph. Then

  * (a)

$\dim(G)-\dim_{f}(G)$ can be arbitrarily large;

  * (b)

$\dim_{k}(G)-\dim_{k,f}(G)$ can be arbitrarily large;

  * (c)

$\dim(G)-\dim_{k,f}(G)$ can be arbitrarily large;

  * (d)

$\frac{\dim_{k,f}(G)}{\dim(G)}$ can be arbitrarily large.

###### Proof.

Let $k\in\mathbb{Z}^{+}$. For (a), (b) and (c), let $G$ be a tree with
$V(G)=M_{2}(G)\cup L(G)$ such that $M_{2}(G)=\\{v_{1},v_{2},\ldots,v_{x}\\}$
is the set of exterior major vertices of $G$ with $ter(v_{i})=\alpha\geq 3$
for each $i\in\\{1,2,\ldots,x\\}$, where $x\geq 1$; see Figure 2. Then
$\dim_{k}(G)\geq\dim(G)=x(\alpha-1)$ by Observation 2.2(b) and Theorem 4.3.
Also, note that $\dim_{k,f}(G)\geq\dim_{f}(G)=\frac{x\alpha}{2}$ by
Observation 2.2(c) and Theorem 3.1(a). Since a function
$g:V(G)\rightarrow[0,1]$ defined by $g(u)=\frac{1}{2}$ for each $u\in L(G)$
and $g(w)=0$ for each $w\in M_{2}(G)=V(G)-L(G)$ is a $k$-truncated resolving
function for $G$ with $g(V(G))=\frac{x\alpha}{2}$,
$\dim_{k,f}(G)\leq\frac{x\alpha}{2}$. So,
$\dim_{k,f}(G)=\dim_{f}(G)=\frac{x\alpha}{2}$. Thus,
$\dim_{k}(G)-\dim_{k,f}(G)\geq\dim(G)-\dim_{k,f}(G)=\dim(G)-\dim_{f}(G)=x(\alpha-1)-\frac{x\alpha}{2}=\frac{x(\alpha-2)}{2}\rightarrow\infty$
as $x\rightarrow\infty$ or $\alpha\rightarrow\infty$.

For (d), let $G=C_{x(k+1)(k+5)}$ for some $x\in\mathbb{Z}^{+}$. Then
$\dim_{k,f}(G)=\frac{x(k+5)}{2}$ by Theorem 3.4 and $\dim(G)=2$. So,
$\frac{\dim_{k,f}(G)}{\dim(G)}=\frac{x(k+5)}{4}\rightarrow\infty$ as
$x\rightarrow\infty$. ∎

$v_{1}$$v_{2}$$v_{3}$$v_{x}$$\ell_{1,1}$$\ell_{1,2}$$\ell_{1,\alpha}$$\ell_{2,1}$$\ell_{2,2}$$\ell_{2,\alpha}$$\ell_{3,1}$$\ell_{3,2}$$\ell_{3,\alpha}$$\ell_{x,1}$$\ell_{x,2}$$\ell_{x,\alpha}$
Figure 2: Trees $G$ such that $\dim(G)-\dim_{f}(G)$,
$\dim_{k}(G)-\dim_{k,f}(G)$ and $\dim(G)-\dim_{k,f}(G)$ can be arbitrarily
large.

Next, we show the existence of non-isomorphic graphs $G$ and $H$ with
$\dim_{k}(G)=\dim_{k}(H)$ and $\dim_{k,f}(G)\neq\dim_{k,f}(H)$ for each
$k\in\mathbb{Z}^{+}$. We recall the following result.

######  Theorem 4.5.

_[11]_ Let $k\in\mathbb{Z}^{+}$. Then

  * (a)

$\dim_{k}(P_{n})=1$ for $2\leq n\leq k+2$;

  * (b)

$\dim_{k}(C_{n})=2$ for $3\leq n\leq 3k+3$, and $\dim_{k}(P_{n})=2$ for
$k+3\leq n\leq 3k+3$;

  * (c)

for $n\geq 3k+4$,

$\dim_{k}(C_{n})=\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.$

######  Remark 4.6.

Let $k\in\mathbb{Z}^{+}$. There exist non-isomorphic graphs $G$ and $H$ such
that $\dim_{k}(G)=\dim_{k}(H)$ and $\dim_{k,f}(G)\neq\dim_{k,f}(H)$. For
$n\geq 3k+4$, $\dim_{k}(C_{n})=\dim_{k}(P_{n})$ by Theorem 4.5 and
$\dim_{k,f}(C_{n})\neq\dim_{k,f}(P_{n})$ for $n\equiv 1\pmod{(2k+2)}$ by
Theorems 3.4 and 3.11(c).

We conclude the paper with some open problems.

######  Question 4.7.

For any tree $T$ and for any $k\in{Z}^{+}$, can we determine $\dim_{k,f}(T)$?

######  Question 4.8.

For any $k\in\mathbb{Z}^{+}$, can we characterize all connected graphs $G$
satisfying $\dim_{k,f}(G)=\dim_{f}(G)$?

######  Question 4.9.

For any $k\in\mathbb{Z}^{+}$, can we characterize all connected graphs $G$
satisfying $\dim_{k}(G)=\dim_{k,f}(G)$?

## References

  * [1] S. Arumugam and V. Mathew, The fractional metric dimension of graphs. Discrete Math. 312 (2012) 1584-1590.
  * [2] S. Arumugam, V. Mathew and J. Shen, On fractional metric dimension of graphs. Discrete Math. Algorithms Appl. 5 (2013) 1350037.
  * [3] 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.
  * [4] 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.
  * [5] J. Currie and O.R. Oellermann, The metric dimension and metric independence of a graph. J. Combin. Math. Combin. Comput. 39 (2001) 157-167.
  * [6] 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.
  * [7] A. Estrada-Moreno, On the ($k,t$)-metric dimension of a graph. Dissertation, Universitat Rovira i Virgili, 2016.
  * [8] A. Estrada-Moreno, I.G. Yero and J.A. Rodríguez-Velázquez, On the ($k,t$)-metric dimension of graphs. Comput. J. 64(5) (2021) 707-720.
  * [9] M. Fehr, S. Gosselin and O.R. Oellermann, The metric dimension of Cayley digraphs. Discrete Math. 306 (2006) 31-41.
  * [10] 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.
  * [11] R.M. Frongillo, J. Geneson, M.E. Lladser, R.C. Tillquist and E. Yi, Truncated metric dimension for finite graphs. submitted111This paper is a result of merging the following two papers: (1) J. Geneson and E. Yi, The distance-$k$ dimension of graphs. arXiv:2106.08303v2; (2) R.C. Tillquist, R.M. Frongillo and M.E. Lladser, Truncated metric dimension for finite graphs. arXiv:2106.14314v1
  * [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 and E. Yi, Broadcast metric dimension. arXiv:2005.07311v1
  * [14] F. Harary and R.A. Melter, On the metric dimension of a graph. Ars Combin. 2 (1976) 191-195.
  * [15] 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.
  * [16] M. Jannesari and B. Omoomi, The metric dimension of the lexicographic product of graphs. Discrete Math. 312(22) (2012) 3349-3356.
  * [17] C.X. Kang, On the fractional strong metric dimension of graphs. Discrete Appl. Math. 213 (2016) 153-161.
  * [18] C.X. Kang and E. Yi, The fractional strong metric dimension of graphs. Lecture Notes in Comput. Sci. 8287 (2013) 84-95.
  * [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] E.R. Scheinerman and D.H. Ullman, Fractional graph theory: A rational approach to the theory of graphs. John Wiley & Sons, New York, 1997.
  * [22] P.J. Slater, Leaves of trees. Congr. Numer. 14 (1975) 549-559.
  * [23] R.C. Tillquist, Low-dimensional embeddings for symbolic data science. Dissertation, University of Colorado, Boulder, 2020.
  * [24] E. Yi, The fractional metric dimension of permutation graphs. Acta Math. Sin. (Engl. Ser.) 31 (2015) 367-382.


# Supervised Fine-tuning Evaluation for Long-term Visual Place Recognition

Farid Alijani  Tampere University
Tampere, Finland
<EMAIL_ADDRESS>Esa Rahtu  Tampere University
Tampere, Finland
<EMAIL_ADDRESS>
###### Abstract

In this paper, we present a comprehensive study on the utility of deep
convolutional neural networks with two state-of-the-art pooling layers which
are placed after convolutional layers and fine-tuned in an end-to-end manner
for visual place recognition task in challenging conditions, including
seasonal and illumination variations. We compared extensively the performance
of deep learned global features with three different loss functions, e.g.
triplet, contrastive and ArcFace, for learning the parameters of the
architectures in terms of fraction of the correct matches during deployment.
To verify effectiveness of our results, we utilized two real world datasets in
place recognition, both indoor and outdoor. Our investigation demonstrates
that fine tuning architectures with ArcFace loss in an end-to-end manner
outperforms other two losses by approximately $1\sim 4\;\%$ in outdoor and
$1\sim 2\;\%$ in indoor datasets, given certain thresholds, for the visual
place recognition tasks.

††publicationid: pubid: 978-1-6654-3288-7/21/$31.00 ©2021 European Union

##  I Introduction

Image retrieval is a problem of searching for a query image in a large image
database given the visual content of an image. Large-scale Visual Place
Recognition (VPR) is commonly formulated as a subcategory of image retrieval
problem to identify images which belong to similar places with same positions
in robotics and autonomous systems [1]. It can generally be extended to
broader areas, including topological mapping, loop closure and drift removal
in geometric mapping and learning scene dynamics for long-term localization
and mapping. Long-term operations in environments can cause significant image
variations including illumination changes, occlusion and scene dynamics [2].

The recognition robustness of VPR systems depends on whether or not the
matched images are taken at the same places in the real world given a certain
threshold. Therefore, the retrieval performance is highly correlated with
feature representation and similarity measurement [3]. One of the crucial
challenges is to extract meaningful information of raw images in order to
mitigate the semantic gap of low level image representation perceived by
machines and high level semantic concept perceived by human [4].

Global feature descriptors are commonly utilized to obtain high image
retrieval performance with compact image representations. Before deep learning
era in computer vision, they were mainly developed by aggregating hand-crafted
local descriptors. Deep Convolutional Neural Networks (DCNNs) are now the core
of the most state-of-the-art computer vision techniques in wide variety of
tasks, including image classification, object detection and image segmentation
[5].

Recent advances of the generic descriptors extracted from DCNNs can learn
discriminatory and human-level representation to provide high-level visual
content of the image patterns [6]. These architectures can potentially learn
features at multiple abstraction levels to map large raw sensory input data to
the output, without relying on human-crafted features [7]. The DCNN-based
global features are high performing descriptors trained with ranking-based or
classification losses [8].

Figure 1: The architecture of our DCNN with the triplet, contrastive and
ArcFace losses used for end-to-end training. A single vector global descriptor
$f(.)$ is extracted to represent an image.

Throughout the past few years, several DCNNs have been designed to address
image classification and objection detection. In this paper, our contribution
is to conduct an all-embracing study on supervised fine-tuning of such DCNNs
with two state-of-the-art pooling layers with learnable parameters, one for
image retreival, i.e., GeM, and one for place recognition, i.e., NetVLAD, in
an end-to-end manner for the VPR task on real world datasets. In our
investigation, we report and analyze the performance of deep learned global
features which are trained with three different loss functions in terms of the
fraction of correct matches of query images compared to the reference images.

The rest of this paper is organized as follows. Section II briefly discusses
the related work. In section III, we provide the baseline methods along with
section IV which explains two real-world indoor and outdoor datasets to
address the VPR task. In section V, we show the experimental results and we
conclude the paper in section VI.

##  II Related Work

Before the rise and dominance of DCNNs, VPR methods utilized conventional
hand-crafted features such as local and global image descriptors, to match
query images with the reference database [9, 10, 11]. However, deep features
have shown more robust performance than handcrafted features to address the
geometric transformations and illumination changes.

DCNN-based VPR methods can be divided into two main categories. 1) Methods
with pre-trained DCNN models, utilized as feature extractor to construct image
representation to measure the image similarity. 2) Methods with fine-tune
models on specific VPR datasets or new architecture to improve the recognition
performance.

Chen et al. [12] introduced the first off-the-shelf DCNN-based VPR system with
features extracted from a pre-trained Overfeat [13] model in challenging
conditions. Sünderhauf et al. [14] evaluated the intermediate conv3 layer of
AlexNet, primarily trained for image classification, as holistic image
representation to match places across condition changes between query and
reference database. Chen et al. [15] trained AmosNet and HybridNet on a large-
scale dataset to address the appearance and viewpoint variations. Lopez et al.
[16] fine-tuned AlexNet pre-trained architecture on ImageNet dataset for VPR
with triplets of images containing original image stacked with similar and
dissimilar pairs. Feature post-processing methods, e.g., feature augmentation
and standardization have shown improvement compared to using raw holistic
DCNN-descriptors [17, 18, 19].

DCNN-based VPR methods can learn robust feature mapping to enable image
comparison using similarity measures such as Euclidean distance. Single
feedforward pass methods take the whole image as an input followed by pooling
or aggregation on the raw features to design more global discriminative
features in which the whole image is described by as single feature vector,
i.e., global descriptor.

A number of architectures have been proposed to address the image
representation with global descriptor: MAC [20], SPoC [21], CroW [22], GeM
[23], R-MAC [24], modified R-MAC [25]. Moreover, there are DCNNs especially
trained for VPR to retreive either global image descriptors, e.g., NetVLAD
[26] or local features, e.g., DELF [27].

In this paper, we selected and fine-tuned two state-of-the-art methods for
global descriptors, e.g., GeM and NetVLAD which are trained in an end-to-end
manner for both indoor and outdoor VPR datasets.

##  III Baseline Methods

###  III-A Pooling Layer

Adding pooling layer after the convolutional layer is a common pattern for
layer ordering of DCNNs to create a new set of the same number of pooled
feature maps. In what follows, we provide a brief summary of GeM and NetVLAD
pooling layers, utilized as pooling layers in this paper:

#### GeM

Radenović et al. [28, 23] adopt the siamese architecture for training. It is
trained using positive and negative image pairs and the loss function enforces
large distances between negative pairs, e.g., images from two distant places
and small distances between positive pairs, e.g., images from the same place.
Feature vectors are global descriptors of the input images and pooled over the
spatial dimensions. The feature responses are computed from $K$ convolutional
layers $\mathcal{X}_{k}$ following with max pooling layers that select the
maximum spatial feature response from each layer of MAC:

$\vec{f}=\left[f_{1}~{}f_{2}~{}\ldots~{}f_{K}\right],~{}f_{k}=\max_{x\in\mathcal{X}_{k}}x\enspace.$
(1)

GeM pooling layer is proposed to modify MAC [20] and SPoC [21] for better
performance. This is a pooling layer which takes $\chi$ as an input and
produces a vector $f=[f_{1},f_{2},f_{i},...,f_{K}]^{T}$ as an output of the
pooling process which results in:

$f_{i}=\left(\frac{1}{|\chi_{i}|}\sum_{x\in\chi_{i}}x^{p_{i}}\right)^{\frac{1}{p_{i}}}$
(2)

MAC and SPoC are special cases of GeM pooling layer depending on how pooling
parameter $p_{k}$ is derived in which $p_{i}\rightarrow\infty$ and $p_{i}=1$
correspond to max-pooling and average pooling, respectively. The GeM feature
vector is a single value per feature map and its dimension varies depending on
different networks, i.e. $K=[256,\;512,\;2048]$.

#### NetVLAD

Function $f$ is defined as the global feature vector for a given image $I$ as
$f(I)$. This function is used to extract the feature vectors from the entire
reference database ${I_{i}}$. Then visual search between $f(q)$, e.g., query
image and the reference images $f(I_{i})$ is performed using Euclidean
distance $d(q,I_{i})$ and by selecting the top-N matches. NetVLAD is inspired
by the conventional VLAD [11] which uses handcrafted SIFT descriptors [29] and
uses VLAD encoding to form $f(I)$.

To learn the representation end-to-end, NetVLAD contains two main building
blocks. 1) Cropped CNN at the last convolutional layer, identified as a dense
descriptor with the output size of $H\times W\times D$, correspond to set of
$D$-dimensional descriptors extracted at $H\times W$ spatial locations. 2)
Trainable generalized VLAD layer, e.g., Netvlad which pools extracted
descriptors into a fixed image representation in which its parameters trained
via backpropagation.

The original VLAD image representation $V$ is $D\times K$ matrix in which $D$
is the dimension of the input local image descriptor ${\vec{x}_{i}}$ and $K$
is the number of clusters. It is reshaped in to a vector after
$L_{2}$-normalization and $(j,k)$ element of $V$ is calculated as follows:

$V(j,k)=\sum_{i=1}^{N}a_{k}(\vec{x}_{i})(x_{i}(j)-c_{k}(j)),$ (3)

where $x_{i}(j)$ and $c_{k}(j)$ are the $j$th dimensions of the $i$th
descriptor and $k$th cluster centers, respectively. $a_{k}(\vec{x}_{i})=0,1$
indicates whether or not descriptor $\vec{x}_{i}$ belongs to $k$th visual
word. Compared to original VLAD, Netvlad layer is differentiable thanks to its
soft assignment of descriptors to multiple clusters:

$V(j,k)=\sum_{i=1}^{N}\frac{e^{w_{k}^{T}x_{i}+b_{k}}}{\sum_{k^{\prime}}e^{w_{k^{\prime}}^{T}x_{i}+b_{k^{\prime}}}}(x_{i}(j)-c_{k^{\prime}}(j))$
(4)

where ${w_{k}}$, ${b_{k}}$ and ${c_{k}}$ are gradient descent optimized
parameters of $k$ clusters.

In our experiments with 64 clusters and $512$-dimensional VGG16 backbone, the
NetVLAD feature vector dimension becomes $512\times 64=32,768$. Arandjelovic
et al. [26] used PCA dimensionality reduction method as a post-processing
stage. However, in our experiment we utilized full size of feature vector.
Since NetVLAD layer can be easily plugged into any other CNN architecture in
an end-to-end manner, we investigate its performance with VGG16 and ResNet50
backbones and report the results in section V.

###  III-B Loss Function

One of the main challenges of feature learning in large-scale DCNN-based VPR
methods is to design an appropriate loss function to improve the the
discriminative power and recognition ability [30]. We evaluated the loss
functions for the VPR task in two categories. 1) Measure the difference
between samples based on the Euclidean space distance, e.g., contrastive loss
and triplet loss. 2) Measure the difference between samples based on angular
space, e.g., ArcFace loss.

#### Contrastive

Given the siamese architecture, the training input consists of image pairs
$(a,b)$ and labels $y(a,b)=\\{0,1\\}$ declaring whether a pair is non-matching
($y=0$) or matching ($y=1$). Contrastive loss [31] acts on matching (positive)
and non-matching (negative) pairs as follows:

$\mathcal{L_{C}}=\begin{cases}{l}(\vec{f}_{a},\vec{f}_{b})\hbox{ for matching
images}\\\ \max\left(0,M-{l}(\vec{f}_{a},\vec{f}_{b})\right)\hbox{
otherwise}\end{cases}$ (5)

where ${l(.)}$ is the pair-wise distance and $M$ is the enforced minimum
margin between the negative pairs. $\vec{f}_{a}$ and $\vec{f}_{b}$ denote the
deep feature vectors of images $I_{a}$ and $I_{b}$ computed using the
convolutional head of a backbone network such as AlexNet, VGGNet or ResNet
which leads to feature vector lengths $K$ of 256, 512 or 2048, respectively.

#### Triplet

The idea of triplet ranking loss is two folds: 1) to obtain training dataset
of tuples $(q,\\{{p_{i}}^{q}\\},\\{{n_{j}}^{q}\\})$ in which for every query
image $q$, there exists set of positives $\\{{p_{i}}^{q}\\}$ with at least one
image matching the query and negatives $\\{{n_{j}}^{q}\\}$, 2) to learn an
image representation $f_{\theta}$ so that
$d_{\theta}(q,{p_{i}}^{q})<d_{\theta}(q,{n_{j}}^{q}),\forall j$ [32].
Accordingly, we utilized supervised ranking loss $\mathcal{L}_{T}$ adopted by
DCNN as a sum of individual losses for all $n^{q}_{j}$ computed as follows:

$\small\mathcal{L}_{T}=\sum_{j}max(\left(|f_{\theta}(q)-f_{\theta}(p^{q}_{i})|^{2}-|f_{\theta}(q)-f_{\theta}(n^{q}_{j})|^{2}+\alpha\right),0),$
(6)

where $\alpha$ is the given margin in meter. If the margin between the
distance to the negative image and to the best matching positive is violated,
the loss is proportional to the degree of violation.

#### ArcFace

Deng et al. [33] propose an Additive Angular Margin Loss (ArcFace) to improve
the discriminative power of the global feature learning by inducing smaller
intra-class appearance variations to stabilize the training process.

In this paper, we adopt ArcFace loss function with $L_{2}$-normalized
$D$-dimensional features $x_{i}\in\mathbb{R}^{D}$ and classifier weights
$W\in\mathbb{R}^{D\times n}$, followed by scaled softmax normalization and
cross-entropy loss for global feature learning tailored for the VPR task,
computed as follows:

$\mathcal{L}_{A}=-\frac{1}{N}\sum_{i=1}^{N}log\frac{e^{s(cos(\theta_{y_{i}}+m))}}{e^{s(cos(\theta_{y_{i}}+m))}+\sum_{j=1,j\neq
y_{i}}^{n}e^{scos\theta_{j}}},$ (7)

where $N$ is the batch size, $s$ is the feature scale, $m$ is the angular
margin and $n=\\{0,1\\}$ is the class label, e.g., binary classification.
$\theta_{y_{i}}$ is the computed angle between the feature and the ground
truth weight. The normalization step on features and weights makes the
predictions only depend on the angle between the feature $x_{i}$ and the
ground-truth weight $W_{y_{i}}$. The learned embedding features are thus
distributed on a hyper-sphere with a radius of $s$.

##  IV Datasets

We evaluated the methods on both outdoor and indoor VPR datasets. We selected
two query sequences with gradually increasing difficulty: 1) Test 01
conditions moderately changed, e.g, time of day or illumination; and 2) Test
02 conditions clearly different from the reference. In the following we
briefly describe the datasets and selection of training, reference and the
three test sequences.

###  IV-A Oxford Radar RobotCar

The Oxford Radar RobotCar dataset [34] contains the ground-truth optimized
radar odometry data from a Navtech CTS350-X Millimetre-Wave FMCW radar. The
data acquisition was conducted in January 2019 over 32 traversals in central
Oxford with a total route of 280 km of urban driving. It addresses a variety
of conditions including weather, traffic, and lighting alterations. The
combination of one Point Grey Bumblebee XB3 trinocular stereo and three Point
Grey Grasshopper2 monocular cameras provide a 360 degree visual coverage of
the scene around the vehicle platform. The Bumblebee XB3 is a 3-sensor multi-
baseline IEEE-1394b stereo camera designed for improved flexibility and
accuracy. It features 1.3 mega-pixel sensors with $66\degree$ HFoV and
$1280\times 960$ image resolution logged at maximum frame rate of 16 Hz. The
three monocular Grasshopper2 cameras with fisheye lenses mounted on the back
of the vehicle are synchronized and logged $1024\times 1024$ images at average
frame rate of 11.1 Hz with $180\degree$ HFoV.

Figure 2: Examples from the Oxford Radar RobotCar outdoor dataset. Top: Images
from the same location in the three selected test sequences: a) Reference:
cloudy b) Test 01: sunny c) Test 02: rainy (Grasshopper2 left monocular
camera). Bottom: the 19 km route of the test sequences, d) satellite view e)
GNSS/INS.

To simplify our experiments we selected images from only one of the cameras,
the Point Grey Grasshopper2 monocular camera (left), despite the fact that
using multiple cameras improve the results. The selected camera points toward
the left side of the road and thus encodes the stable urban environment such
as the buildings (Figure 2).

From the dataset, we selected sequences for a training set, e.g., supervised
fine-tuning, a reference against which the query images from the test sequence
are matched and three distinct test sets: 1) the different day but
approximately at same time and 2) the different day and different time along
with different weather conditions. Table I summarizes different sequences used
for training, gallery and testing.

TABLE I: The Radar RobotCar outdoor sequences used in our experiments.

Sequence | Size | Date | Start [GMT] | Condition
---|---|---|---|---
Train | 37,724 | Jan. 10 2019 | 11:46 | Sunny
Reference | 36,660 | Jan. 10 2019 | 12:32 | Cloudy
Test 01 | 32,625 | Jan. 11 2019 | 12:26 | Sunny
Test 02 | 28,633 | Jan. 16 2019 | 14:15 | Rainy

###  IV-B COLD

The CoSy Localization Database (COLD) [35] presents annotated data sequences
acquired using visual and laser range sensors on a mobile platform. The
database represents an effort to provide a large-scale, flexible testing
environment for evaluating mainly vision-based topological localization and
semantic knowledge extraction methods aiming to work on mobile robots in
realistic indoor scenarios. The COLD database consists of several video
sequences collected in three different indoor laboratory environments located
in three different European cities: the Visual Cognitive Systems Laboratory at
the University of Ljubljana, Slovenia; the Autonomous Intelligent Systems
Laboratory at the University of Freiburg, Germany; and the Language Technology
Laboratory at the German Research Center for Artificial Intelligence in
Saarbrücken, Germany.

Data acquisition were performed using three different robotic platforms (an
ActivMedia People Bot, an ActiveMedia Pioneer-3 and an iRobot ATRV-Mini) with
two Videre Design MDCS2 digital cameras to obtain perspective and
omnidirectional views. Each frame is registered with the associated absolute
position recovered using laser and odometry data and annotated with a label
representing the corresponding place. The data were collected from a path
visiting several rooms and under different illumination conditions, including
cloudy, night and sunny.

Figure 3: Examples from the COLD indoor database [35]. Images of same location
in different sequences: a) Reference: Cloudy-seq1 b) Test 01: Cloudy-seq2, c)
Test 02: Night-seq3, d) Map view of the lab: blue dashes: standard path, i.e.,
short path, red dashes: extended path, arrows indicate the direction of
driving the robot and e) Robot path of approximately 50 m.

For our experiments, we selected the extended, e.g., long path on Map B of
Saarbrücken laboratory. The training sequence is Sunny-seq3, gallery sequence
is Cloudy-seq1, and the three test sequences are 1) Sunny-seq1, 2) Cloudy-seq2
and 3) Night-seq3. See Figure 3 for examples. We used the captured images
acquired using the monocular center camera form this setup. Table II
summarizes different sequences used for training, reference and testing.

TABLE II: The COLD indoor sequences used in our experiments.

Sequence | Size | Date | Start [GMT] | Condition
---|---|---|---|---
Train | 1036 | July 7 2006 | 14:59 | Sunny
Reference | 1371 | July 7 2006 | 17:05 | Cloudy
Test 01 | 1021 | July 7 2006 | 18:59 | Cloudy
Test 02 | 970 | July 7 2006 | 20:34 | Night

##  V Experimental Results

We illustrate the utility of two DCNN architectures with GeM and NetVLAD
pooling layers for VPR taks, trained and fine-tuned for the indoor and outdoor
VPR datasets with three different loss functions. The experiments aim to
address the following research questions: 1) what is the accuracy level of
place recognition? 2) what is the impact of fine tuning with different loss
functions, given Euclidean space distance or angular space?

Given the reference database and query images, we extract the sparse feature
vectors and compute the similarity between each query image and the reference
database using $L_{2}$ distance metric. Similar reference feature vectors have
the lowest $L_{2}$ distance with the query. Similar to [36], we calculate
Fraction of Correct Matches (FCM) as follows:

$FCM=\frac{Correct\;Matches}{\sum Query\;Images}\times 100,$ (8)

which corresponds to the proportion of the query images which are correctly
matched within a certain accuracy threshold $\tau$.

###  V-A Oxford Radar RobotCar

Depending on which loss function we utilized to fine-tune the DCNN-based VPR
methods for Oxford Radar RobotCar dataset, we report the FCM for two test
queries. For this dataset, we report the results within meter accuracy
threshold, e.g., $\tau=2\sim 25\;m$.

TABLE III: FCM for Oxford Radar RobotCar dataset, given trained and fine-tuned
model with Triplet, Contrastive and ArcFace loss function.

Method | BB | $\tau=25~{}m$ | $\tau=10~{}m$ | $\tau=5~{}m$ | $\tau=2~{}m$
---|---|---|---|---|---
|  | TRIPLET |
Test 01 (diff. day, same time) |  |  |  |
GeM [23] | VGG16 | 90.89 | 89.36 | 60.11 | 42.21
| ResNet50 | 95.18 | 93.40 | 61.61 | 47.88
NetVLAD [26] | VGG16 | 56.59 | 48.89 | 38.42 | 17.01
| ResNet50 | 57.82 | 51.60 | 42.13 | 23.83
Test 02 (diff. day and time) |  |  |  |
GeM [23] | VGG16 | 89.09 | 86.63 | 82.92 | 62.53
| ResNet50 | 91.74 | 88.92 | 84.20 | 64.86
NetVLAD [26] | VGG16 | 38.48 | 31.61 | 24.55 | 24.07
| ResNet50 | 47.69 | 42.94 | 37.72 | 22.23
|  | CONTRASTIVE |
Test 01 (diff. day, same time) |  |  |  |
GeM [23] | VGG16 | 72.69 | 70.30 | 64.33 | 31.92
| ResNet50 | 71.84 | 68.41 | 60.71 | 32.71
NetVLAD [26] | VGG16 | 47.30 | 42.44 | 33.90 | 14.03
| ResNet50 | 50.02 | 46.67 | 34.86 | 14.19
Test 02 (diff. day and time) |  |  |  |
GeM [23] | VGG16 | 60.38 | 58.94 | 56.05 | 42.78
| ResNet50 | 56.88 | 52.51 | 48.39 | 33.87
NetVLAD [26] | VGG16 | 30.94 | 25.53 | 20.69 | 11.13
| ResNet50 | 41.94 | 38.33 | 32.09 | 18.30
|  | ARCFACE |
Test 01 (diff. day, same time) |  |  |  |
GeM [23] | VGG16 | 91.37 | 89.37 | 66.16 | 42.02
| ResNet50 | 96.51 | 94.08 | 68.91 | 48.09
NetVLAD [26] | VGG16 | 36.11 | 25.53 | 22.40 | 9.65
| ResNet50 | 70.54 | 63.35 | 52.42 | 23.83
Test 02 (diff. day and time) |  |  |  |
GeM [23] | VGG16 | 89.64 | 86.63 | 82.83 | 62.42
| ResNet50 | 92.00 | 89.00 | 84.62 | 65.08
NetVLAD [26] | VGG16 | 33.58 | 28.05 | 23.12 | 13.36
| ResNet50 | 49.68 | 44.46 | 38.07 | 22.23

Table III indicate that ArcFace loss function outperforms the triplet and
contrastive losses by approximately $1\sim 4\;\%$ when utilized in training
time. Furthermore, supervised fine-tuning of the DCNN with GeM pooling layer
demonstrates higher robustness in finding the correct matches for queries in
the reference dataset, e.g., higher FCM.

###  V-B COLD

In this section, we present FCM results for the indoor COLD database, given
the trained and fine-tuned models with GeM and NetVLAD pooling layers and
Tiplet, Contrastive and ArcFace loss functions. For indoor dataset, we report
the results within centimeter accuracy threshold, e.g., $\tau=25\sim 100\;cm$.

TABLE IV: FCM for COLD database, given trained and fine-tuned model with
Triplet, Contrastive and ArcFace loss function.

Method | BB | $\tau=100~{}cm$ | $\tau=75~{}cm$ | $\tau=50~{}cm$ | $\tau=25~{}cm$
---|---|---|---|---|---
|  | TRIPLET |
Test 01 (cloudy) |  |  |  |
GeM [23] | VGG16 | 94.32 | 90.11 | 82.66 | 46.33
| ResNet50 | 93.18 | 94.03 | 84.62 | 46.52
NetVLAD [26] | VGG16 | 90.60 | 85.80 | 75.51 | 43.98
| ResNet50 | 92.65 | 89.72 | 79.53 | 45.05
Test 02 (night) |  |  |  |
GeM [23] | VGG16 | 84.54 | 82.47 | 75.26 | 43.71
| ResNet50 | 90.10 | 85.94 | 80.21 | 46.72
NetVLAD [26] | VGG16 | 75.88 | 74.33 | 65.26 | 42.99
| ResNet50 | 78.25 | 77.32 | 67.73 | 42.68
|  | CONTRASTIVE |
Test 01 (cloudy) |  |  |  |
GeM [23] | VGG16 | 89.23 | 86.58 | 79.33 | 43.19
| ResNet50 | 94.52 | 91.77 | 85.01 | 47.40
NetVLAD [26] | VGG16 | 88.54 | 83.64 | 74.24 | 42.21
| ResNet50 | 90.40 | 87.46 | 76.49 | 45.05
Test 02 (night) |  |  |  |
GeM [23] | VGG16 | 80.82 | 78.35 | 71.86 | 44.12
| ResNet50 | 82.06 | 79.48 | 73.30 | 44.54
NetVLAD [26] | VGG16 | 74.23 | 72.37 | 65.05 | 41.03
| ResNet50 | 75.05 | 74.12 | 66.60 | 42.89
|  | ARCFACE |
Test 01 (cloudy) |  |  |  |
GeM [23] | VGG16 | 95.10 | 91.48 | 83.25 | 48.19
| ResNet50 | 96.53 | 94.32 | 84.75 | 46.33
NetVLAD [26] | VGG16 | 89.52 | 82.57 | 72.18 | 43.78
| ResNet50 | 91.19 | 87.56 | 78.65 | 45.05
Test 02 (night) |  |  |  |
GeM [23] | VGG16 | 86.60 | 83.61 | 76.19 | 44.64
| ResNet50 | 93.45 | 86.49 | 81.14 | 47.01
NetVLAD [26] | VGG16 | 76.08 | 74.43 | 66.39 | 42.06
| ResNet50 | 72.37 | 69.59 | 62.68 | 37.22

According to Table IV, trained and fine-tuned models with ArcFace loss
functions results in more robust performance, $1\sim 2\;\%$, for finding the
correct matches in reference database. Moreover, GeM pooling layer outperforms
NetVLAD when utilized as a global feature vectors.

We used VGG16 and ResNet50 backbones in our investigations. Although the size
of the COLD indoor dataset is relatively smaller than Oxford Radar RobotCar
and results of ResNet50 approximately outperforms VGG16, it is computationally
more affordable to utilize the VGG16 architecture as the backbone due to
smaller size.

##  VI Conclusion

In this paper, we presented a through investigation of DCNN-based VPR methods,
primarily trained and fine-tuned in an end-to-end manner with two pooling
layers, e.g., GeM and NetVLAD along with three different loss functions, e.g.,
triplet, contrastive and ArcFace loss functions.

First, the outperforming validity of supervised fine-tuning the DCNN
architechtures, purely trained for classification problems, is comprehensively
studied for two real world datasets designed for place recognition in variety
of challenging conditions, including seasonal and illumination variations.

Second, the results of correctly matched queries with reference database
indicate that supervised fine-tuning the DCNN architectures with ArcFace loss
outperforms triplet and contrastive losses for indoor and outdoor datasets
within a certain accuracy threshold. Our findings also demonstrate that GeM
pooling layer outperforms NetVLAD to extract global feature vectors in both
indoor and outdoor datasets.

## References

  * [1] X. Zhang, L. Wang, and Y. Su, “Visual place recognition: A survey from deep learning perspective,” _Pattern Recognition_ , p. 107760, 2020.
  * [2] Z. Xin, X. Cui, J. Zhang, Y. Yang, and Y. Wang, “Visual place recognition with cnns: From global to partial,” in _2017 Seventh International Conference on Image Processing Theory, Tools and Applications (IPTA)_ , 2017, pp. 1–6.
  * [3] M. Tzelepi and A. Tefas, “Deep convolutional learning for content based image retrieval,” _Neurocomputing_ , vol. 275, pp. 2467 – 2478, 2018.
  * [4] J. Wan, D. Wang, S. C. H. Hoi, P. Wu, J. Zhu, Y. Zhang, and J. Li, “Deep learning for content-based image retrieval: A comprehensive study,” in _Proceedings of the 22nd ACM International Conference on Multimedia_ , ser. MM ’14. New York, NY, USA: Association for Computing Machinery, 2014, p. 157–166.
  * [5] J. Gu, Z. Wang, J. Kuen, L. Ma, A. Shahroudy, B. Shuai, T. Liu, X. Wang, G. Wang, J. Cai, and T. Chen, “Recent advances in convolutional neural networks,” _Pattern Recognition_ , vol. 77, pp. 354 – 377, 2018.
  * [6] X. Ou, H. Ling, L. Yan, and M. Liu, “Convolutional neural codes for image retrieval,” in _Signal and Information Processing Association Annual Summit and Conference (APSIPA), 2014 Asia-Pacific_ , 2014, pp. 1–10.
  * [7] R. R. Saritha, V. Paul, and P. G. Kumar, “Content based image retrieval using deep learning process,” _Cluster Comput._ , vol. 22, no. 2, pp. 4187–4200, Mar 2019.
  * [8] B. Cao, A. Araújo, and J. Sim, “Unifying deep local and global features for efficient image search,” _ArXiv_ , vol. abs/2001.05027, 2020.
  * [9] M. J. Milford and G. F. Wyeth, “Seqslam: Visual route-based navigation for sunny summer days and stormy winter nights,” in _2012 IEEE International Conference on Robotics and Automation_ , 2012, pp. 1643–1649.
  * [10] M. Cummins and P. Newman, “Appearance-only slam at large scale with fab-map 2.0,” _The International Journal of Robotics Research_ , vol. 30, no. 9, pp. 1100–1123, 2011. [Online]. Available: https://doi.org/10.1177/0278364910385483
  * [11] H. Jégou, M. Douze, C. Schmid, and P. Pérez, “Aggregating local descriptors into a compact image representation,” in _2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition_ , 2010, pp. 3304–3311.
  * [12] Z. Chen, O. Lam, A. Jacobson, and M. Milford, “Convolutional neural network-based place recognition,” _ArXiv_ , vol. abs/1411.1509, 2014.
  * [13] P. Sermanet, D. Eigen, X. Zhang, M. Mathieu, R. Fergus, and Y. LeCun, “Overfeat: Integrated recognition, localization and detection using convolutional networks,” 2014.
  * [14] N. Sünderhauf, S. Shirazi, F. Dayoub, B. Upcroft, and M. Milford, “On the performance of convnet features for place recognition,” in _2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , Sep. 2015, pp. 4297–4304.
  * [15] Z. Chen, A. Jacobson, N. Sünderhauf, B. Upcroft, L. Liu, C. Shen, I. Reid, and M. Milford, “Deep learning features at scale for visual place recognition,” in _2017 IEEE International Conference on Robotics and Automation (ICRA)_ , 2017, pp. 3223–3230.
  * [16] M. Lopez-Antequera, R. Gomez-Ojeda, N. Petkov, and J. Gonzalez-Jimenez, “Appearance-invariant place recognition by discriminatively training a convolutional neural network,” _Pattern Recognition Letters_ , vol. 92, pp. 89 – 95, 2017.
  * [17] S. Garg, N. Suenderhauf, and M. Milford, “Don’t look back: Robustifying place categorization for viewpoint- and condition-invariant place recognition,” in _2018 IEEE International Conference on Robotics and Automation (ICRA)_ , 2018, pp. 3645–3652.
  * [18] Y. Hou, H. Zhang, and S. Zhou, “Convolutional neural network-based image representation for visual loop closure detection,” in _2015 IEEE International Conference on Information and Automation_ , 2015, pp. 2238–2245.
  * [19] H. Jégou and O. Chum, “Negative Evidences and Co-occurences in Image Retrieval: The Benefit of PCA and Whitening,” in _Computer Vision – ECCV 2012_. Berlin, Germany: Springer, Oct 2012, pp. 774–787.
  * [20] H. Azizpour, A. S. Razavian, J. Sullivan, A. Maki, and S. Carlsson, “From generic to specific deep representations for visual recognition,” in _2015 IEEE Conference on Computer Vision and Pattern Recognition Workshops (CVPRW)_ , 2015, pp. 36–45.
  * [21] A. B. Yandex and V. Lempitsky, “Aggregating local deep features for image retrieval,” in _2015 IEEE International Conference on Computer Vision (ICCV)_ , 2015, pp. 1269–1277.
  * [22] Y. Kalantidis, C. Mellina, and S. Osindero, “Cross-Dimensional Weighting for Aggregated Deep Convolutional Features,” in _Computer Vision – ECCV 2016 Workshops_. Cham, Switzerland: Springer, Sep 2016, pp. 685–701.
  * [23] F. Radenović, G. Tolias, and O. Chum, “Fine-tuning cnn image retrieval with no human annotation,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 41, no. 7, pp. 1655–1668, 2019.
  * [24] G. Tolias, R. Sicre, and H. Jégou, “Particular object retrieval with integral max-pooling of cnn activations,” 2016.
  * [25] A. Gordo, J. Almazán, J. Revaud, and D. Larlus, “End-to-End Learning of Deep Visual Representations for Image Retrieval,” _Int. J. Comput. Vision_ , vol. 124, no. 2, pp. 237–254, Sep 2017.
  * [26] R. Arandjelovic, P. Gronat, A. Torii, T. Pajdla, and J. Sivic, “NetVLAD: Cnn architecture for weakly supervised place recognition,” _TPAMI_ , 2018.
  * [27] H. Noh, A. Araujo, J. Sim, T. Weyand, and B. Han, “Large-scale image retrieval with attentive deep local features,” in _2017 IEEE International Conference on Computer Vision (ICCV)_ , 2017, pp. 3476–3485.
  * [28] F. Radenović, G. Tolias, and O. Chum, “CNN image retrieval learns from BoW: Unsupervised fine-tuning with hard examples,” in _ECCV_ , 2016.
  * [29] D. G. Lowe, “Distinctive Image Features from Scale-Invariant Keypoints,” _Int. J. Comput. Vision_ , vol. 60, no. 2, pp. 91–110, Nov 2004.
  * [30] Q. Wang, Y. Ma, K. Zhao, and Y. Tian, “A Comprehensive Survey of Loss Functions in Machine Learning,” _Ann. Data. Sci._ , pp. 1–26, Apr 2020\.
  * [31] S. Chopra, R. Hadsell, and Y. LeCun, “Learning a similarity metric discriminatively with application to face verification,” in _CVPR_ , 2005\.
  * [32] F. Schroff, D. Kalenichenko, and J. Philbin, “Facenet: A unified embedding for face recognition and clustering,” in _2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2015, pp. 815–823.
  * [33] J. Deng, J. Guo, N. Xue, and S. Zafeiriou, “Arcface: Additive angular margin loss for deep face recognition,” in _2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019, pp. 4685–4694.
  * [34] D. Barnes, M. Gadd, P. Murcutt, P. Newman, and I. Posner, “The oxford radar robotcar dataset: A radar extension to the oxford robotcar dataset,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_ , 2020, pp. 6433–6438.
  * [35] A. Pronobis and B. Caputo, “Cold: The cosy localization database,” _The International Journal of Robotics Research_ , vol. 28, no. 5, pp. 588–594, 2009\. [Online]. Available: https://doi.org/10.1177/0278364909103912
  * [36] F. Aliajni and E. Rahtu, “Deep learning off-the-shelf holistic feature descriptors for visual place recognition in challenging conditions,” in _2020 IEEE 22nd International Workshop on Multimedia Signal Processing (MMSP)_ , 2020, pp. 1–6.