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 SX is said to be a k -metric generator for X if and only if for any pair of different points u, vX, there exist at least k points w_1, w_2, … w_kS such that d(u, w_i)d(v, w_i), for all i{1, … k}. Let R_k(X) be the set of metric generators for X . The k -metric dimension _k(X) of (X, d) is defined as equation*_k(X)={|S|: SR_k(X)}.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→ N{0} is defined by d_t(x, y)={d(x, y), t} from the geodesic distance d in G and a positive integer t . The case tD(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 .