Login New user?  
01-Applied Mathematics & Information Sciences
An International Journal


Volumes > Volume 9 > No. 6


The k-Metric Dimension of a Graph

PP: 2829-2840
Alejandro Estrada-Moreno, Juan A. Rodríguez-Velázquez, Ismael G. Yero,
As a generalization of the concept of a metric basis, this article introduces the notion of k-metric basis in graphs. Given a connected graph G = (V,E), a set S ⊆V is said to be a k-metric 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 k-metric generator of minimum cardinality is called a k-metric basis and its cardinality the k-metric dimension of G. A connected graph G is k-metric dimensional if k is the largest integer such that there exists a k-metric basis for G. We give a necessary and sufficient condition for a graph to be k-metric dimensional and we obtain several results on the r-metric dimension, r ∈ {1, . . . , k}.

  Home   About us   News   Journals   Conferences Contact us Copyright naturalspublishing.com. All Rights Reserved