Comparing the metric and strong dimensions of graphs

详细信息    查看全文

• 作者：Gaia Moravcik^a ; ^{gaiamoravcik@gmail.com} ; Ortrud R. Oellermann^a ; ^{o.oellermann@uwinnipeg.ca} ; Samuel Yusim^b ; ^{syusim@uwaterloo.ca}
• 关键词：Metric dimension ; Strong dimension ; Trees ; Cographs ; Bounds ; Algorithms ; Complexity ; Extremal results ; Split graphs
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：31 March 2017
• 年：2017
• 卷：220
• 期：Complete
• 页码：68-79
• 全文大小：479 K
• 卷排序：220

文摘

Let GG be a graph and u,vu,v be any two distinct vertices of GG. A vertex ww of GGresolves  uu and vv if the distance between uu and ww does not equal the distance between vv and ww. A set WW of vertices of GG is a resolving set for GG if every pair of vertices of GG is resolved by some vertex of WW. The minimum cardinality of a resolving set for GG is the metric dimension  , denoted by dim(G)dim(G). If GG is a connected graph, then a vertex wwstrongly resolves   two vertices uu and vv if there is a shortest u–wu–w path containing vv or a shortest v–wv–w path containing uu. A set SS of vertices is a strong resolving set   for GG if every pair of vertices is strongly resolved by some vertex of SS and the minimum cardinality of a strong resolving set is called the strong dimension   of GG and is denoted by sdim(G)sdim(G). Both the problem of finding the metric dimension and the problem of finding the strong dimension of a graph are known to be NP-hard. It is known that the strong dimension can be polynomially transformed to the vertex covering problem for which good approximation algorithms are known. The metric dimension is a lower bound for the strong dimension. In this paper we compare the metric and strong dimensions of graphs. We describe all trees for which these invariants are the same and determine the class of trees for which the difference between these invariants is a maximum. We observe that there is no linear upper bound for the strong dimension of trees in terms of the metric dimension. For cographs we show that sdim(G)≤3dim(G)sdim(G)≤3dim(G) and that this bound is asymptotically sharp. It is known that the problem of finding the metric dimension of split graphs is NP-hard. We show that the strong dimension of connected split graphs can be found in polynomial time.