The k-metric dimension

Ron Adar () and Leah Epstein ()
Additional contact information
Ron Adar: University of Haifa
Leah Epstein: University of Haifa

Journal of Combinatorial Optimization, 2017, vol. 34, issue 1, No 1, 30 pages

Abstract: Abstract For an undirected graph $$G=(V,E)$$ G = ( V , E ) , a vertex $$\tau \in V$$ τ ∈ V separates vertices u and v (where $$u,v\in V$$ u , v ∈ V , $$u\ne v$$ u ≠ v ) if their distances to $$\tau $$ τ are not equal. Given an integer parameter $$k \ge 1$$ k ≥ 1 , a set of vertices $$L\subseteq V$$ L ⊆ V is a feasible solution, if for every pair of distinct vertices, u, v, there are at least k distinct vertices $$\tau _{1},\tau _{2},\ldots ,\tau _{k}\in L$$ τ 1 , τ 2 , … , τ k ∈ L , each separating u and v. Such a feasible solution is called a landmark set, and the k-metric dimension of a graph is the minimal cardinality of a landmark set for the parameter k. The case $$k=1$$ k = 1 is a classic problem, where in its weighted version, each vertex v has a non-negative cost, and the goal is to find a landmark set with minimal total cost. We generalize the problem for $$k \ge 2$$ k ≥ 2 , introducing two models, and we seek for solutions to both the weighted version and the unweighted version of this more general problem. In the model of all-pairs (AP), k separations are needed for every pair of distinct vertices of V, while in the non-landmarks model (NL), such separations are required only for pairs of distinct vertices in $$V \setminus L$$ V \ L . We study the weighted and unweighted versions for both models (AP and NL), for path graphs, complete graphs, complete bipartite graphs, and complete wheel graphs, for all values of $$k \ge 2$$ k ≥ 2 . We present algorithms for these cases, thus demonstrating the difference between the two new models, and the differences between the cases $$k=1$$ k = 1 and $$k \ge 2$$ k ≥ 2 .

Keywords: Resolving set; Metric dimension; Wheel graph (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-016-0073-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:34:y:2017:i:1:d:10.1007_s10878-016-0073-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-016-0073-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().