2016/05/21 by Alejandro Estrada‐Moreno, Estrada-Moreno, A., Ismael G. Yero +3
Computer Science · #05C12 #05C76 #54E35 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.1605.06709
openalex publication_date 2016/05/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let (X,d) be a metric space. A set S⊆ X is said to be a k-metric generator for X if and only if for any pair of different points u,v∈ X, there exist at least k points w1,w2, … wk∈ S such that d(u,wi)≠ d(v,wi), \rm for all i∈ \1, … k\. Let Rk(X) be the set of metric generators for X. The k-metric dimension dimk(X) of (X,d) is defined as dimk(X)=inf\|S|: S∈ Rk(X)\. Here, we discuss the k-metric dimension of (V,dt), where V is the set of vertices of a simple graph G and the metric dt:V× V→ ℕ∪ \0\ is defined by dt(x,y)=min\d(x,y),t\ from the geodesic distance d in G and a positive integer t. The case t≥ D(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.