On The (k, t)-Metric Dimension Of Graphs. (8th April 2020) - Estrada-Moreno, A; Yero, I G; Rodríguez-Velázquez, J A
Abstract: Let $(X, d)$ be a metric space. A set $S\subseteq X$ is said to be a $k$ -metric generator for $X$ if and only if for any pair of different points $u, v\in X$, there exist at least $k$ points $w_1, w_2, … w_k\in S$ such that $d(u, w_i)\ne d(v, w_i), \; for all\; i\in \{1, … k\}.$ Let $\mathcal{R}_k(X)$ be the set of metric generators for $X$ . The $k$ -metric dimension $\dim _k(X)$ of $(X, d)$ is defined as $$\begin{equation*}\dim_k(X)=\inf\{|S|:\, S\in \mathcal{R}_k(X)\}.\end{equation*}$$ Here, we discuss the $k$ -metric dimension of $(V, d_t)$, where $V$ is the set of vertices of a simple graph $G$ and the metric $d_t:V× V→ \mathbb{N}\cup \{0\}$ is defined by $d_t(x, y)=\min \{d(x, y), t\}$ from the geodesic distance $d$ in $G$ and a positive integer $t$ . The case $t\ge D(G)$, where $D(G)$ denotes the diameter of $G$, corresponds to the original theory of $k$ -metric dimension, and the case $t=2$ corresponds to the theory of $k$ -adjacency dimension. Furthermore, this approach allows us to extend the theory of $k$ -metric dimension to the general case of non-necessarily connected graphs. Finally, we analyse the computational complexity of determining the $k$ -metric dimension of $(V, d_t)$ for the metric $d_t$ .