Computing the k-metric dimension of graphs

详细信息    查看全文

• 作者：Ismael G. Yero ; ^a ; ^{ismael.gonzalez@uca.es} ; Alejandro Estrada-Moreno^b ; ^{alejandro.estrada@urv.cat} ; Juan A. Rodrí ; guez-Velá ; zquez^b ; ^{juanalberto.rodriguez@urv.cat}
• 关键词：k-metric dimension ; k-metric dimensional graph ; Metric dimension ; NP-complete problem ; NP-hard problem ; Graph algorithms
• 刊名：Applied Mathematics and Computation
• 出版年：2017
• 出版时间：1 May 2017
• 年：2017
• 卷：300
• 期：Complete
• 页码：60-69
• 全文大小：541 K
• 卷排序：300

文摘

Given a connected graph G=(V,E),G=(V,E), a set S ⊆ V is a k-metric generator for G if for any two different vertices u, v ∈ V, there exist at least k   vertices w1,…,wk∈Sw1,…,wk∈S such that dG(u, wi) ≠ dG(v, wi  ) for every i∈{1,…,k}i∈{1,…,k}. A metric generator of minimum cardinality is called a k-metric basis and its cardinality the k-metric dimension of G. We make a study concerning the complexity of some k-metric dimension problems. For instance, we show that the problem of computing the k-metric dimension of graphs is NP-hard. However, the problem is solved in linear time for the particular case of trees.