The k-metric dimension of a graph

Original · EN

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 w₁,w₂,...,wₖ∈ S such that dG(u,wᵢ)≠ dG(v,wᵢ) for every i∈ {1,...,k}. A 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 k-metric dimension.