


The kMetric Dimension of a Graph 

PP: 28292840 

Author(s) 

Alejandro EstradaMoreno,
Juan A. RodríguezVelázquez,
Ismael G. Yero,


Abstract 

As a generalization of the concept of a metric basis, this article introduces the notion of kmetric basis in graphs. Given a
connected graph G = (V,E), a set S ⊆V is said to be a kmetric generator for G if the elements of any pair of different vertices of G
are distinguished by at least k elements of S, i.e., for any two different vertices u, v ∈V, there exist at least k vertices w1,w2, . . . ,wk ∈ S
such that dG(u,wi) 6= dG(v,wi) for every i ∈ {1, . . . , k}. A kmetric generator of minimum cardinality is called a kmetric basis and its
cardinality the kmetric dimension of G. A connected graph G is kmetric dimensional if k is the largest integer such that there exists a
kmetric basis for G. We give a necessary and sufficient condition for a graph to be kmetric dimensional and we obtain several results
on the rmetric dimension, r ∈ {1, . . . , k}. 



