Algorithmic Aspects On The Minimal Doubly Resolving Set Problem Of Graphs

Resolving sets were independently defined in the 1970s by Slater,Harary and Melter.If S is a resolving set of G,then for every pair of vertices u,v?V(G),there exists x?S,such that d_G(u,x)?d_G(v,x).The size of the minimum cardinality of a resolving set is called the metric dimension.The problem of determining the minimum cardinality of a resolving set is called the metric dimension problem.Doubly resolving sets were introduced by Cáceres et al.as a tool for researching resolving sets of Cartesian products of graphs.If S is a doubly resolving set of a con-nected graph G with order not less than 2,then for every pair of vertices u,v?V(G),there exist x,y?S,such that d_G(u,x)-d_G(u,y)?d_G(v,x)-d_G(v,y).The size of the minimum cardinality of a doubly resolving set is denoted by?(G).The problem of determining the minimum cardinality of a doubly resolving set is called the minimal doubly resolving set problem.The thesis mainly research the minimal doubly resolving set problems on special graphs.Firstly,we research the minimal doubly resolving set problems in k-edge-augmented trees.We prove that if G is a k-edge-augmented tree with?(G)?2,then?(G)?2k+1.Moreover,we prove that if G has a cut-vertex or k=2,then?(G)?2k,and the bound is tight.We characterize the values of?(G)for the 2-edge-augmented trees G with?(G)?2,and give a linear time algorithm to compute?(G).Next,we research the minimal doubly resolving set problems in Hamming graphs,hypercubes and folded hypercubes.We prove that the minimal doubly resolving set problem in hypercubes is equivalent to the coin weighing problem.Then we answer an open question on the minimal doubly resolving set problem in hypercubes.By estab-lishing connections between problems,we give some asymptotic results for the minimal doubly resolving set problem in Hamming graphs and the metric dimension problems in folded hypercubes,and disprove a conjecture on the metric dimension problem in folded hypercubes.Using the Lindstr?m's method for the coin weighing problem,we give an efficient algorithm for the minimal doubly resolving set problem in hypercubes and report some new upper bounds for the coin weighing problem,as well as the metric dimension problem and the minimal doubly resolving set problem in hypercubes.Besides,we research the minimal doubly resolving set problems in line graphs.We give the formula of the minimum cardinality of a doubly resolving set of a line graph of a tree.It leads a linear time algorithm to solve the minimal doubly resolving set problem in line graphs of trees.We show the upper bound and the lower bound of the minimum cardinality of a doubly resolving set of a line graph.Moreover,the upper bound and the lower bound are tight.Finally,we prove that the minimal doubly resolving set problem is NP-hard even restrict on split graphs,bipartite graphs,co-bipartite graphs and line graphs of bipartite graphs.