The Resolving Set Problem Of Undirected De Bruijn Graph

Suppose G=(V,E)is a simple connected graph and S is a subset of V and d_G(v,w)means the distance between vertices v,w?V.A set S is a resolving set of G if for any two different vertices v,w?V,there exists a vertex x E S making d_G(x,u)?d_G(x,v).The number of the minimal resolving set of the graph G is the metric dimension of G.The resolving set problem is to find the minimal resolving set of a graph,namely determine the metric dimension of a graph.Suppose G=(V,E)and V={x₁x₂…x_n|x_i?{0,1,…d-1}}.For every vertex x=x₁x₂…x_n,there is an arc from x=x₁x₂…xn to y=x₂…x_nk,where k E{0,1,…,d-1}.We call G is De Bruijn digraph denoted as B(d,n).We have undirected De Bruijn graph by removing the direction of each edge and multiplicities and loops of B(d,n),denoted by UB(d,n).This paper,we give a upper bound of metric dimension of UB(d,n)when n?5,and we obtain the exact value of the metric dimension of UB(2,n)when n?4.