On The (k, t)-Metric Dimension Of Graphs. (8th April 2020)

• Record Type: Journal Article
• Authors: Estrada-Moreno, A; Yero, I G; Rodríguez-Velázquez, J A
• Is Part Of: Computer journal. Volume 64:Number 5(2021)
• Page Start: 707
• Page End: 720
• Publication Date: 2020-04-08
• Subjects: metric dimension -- k-metric dimension -- k-adjacency dimension -- metric space -- nondeterministic polynomial time; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxaa009
• Languages: English
• ISSNs: 0010-4620

Abstract

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, \ldots w_k\in S$ such that $d(u, w_i)\ne d(v, w_i), \; \textrm{for all}\; i\in \{1, \ldots 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\times V\rightarrow \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$ .