| |
|
|
|
The k-Metric Dimension of a Graph |
|
|
|
PP: 2829-2840 |
|
|
|
Author(s) |
|
|
|
Alejandro Estrada-Moreno,
Juan A. Rodríguez-Velázquez,
Ismael G. Yero,
|
|
|
|
Abstract |
|
|
| 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}. |
|
|
|
|
 |
|
