The Dimensions Of Graphs And The Constructions Of Their Bases

Let G = (V,E) be a connected graph and W = {wi, w?,..., Wk] an ordered set of V. Given v € V, the representation of v with respect to W is the k ?vector r(v\W) = (d(v, Wi), d(v,w?),...,d(u, Wfc)), where d(x,y) denote the distance between x and y in G. The set W is a resolving set of G if r(u|W) = r(u|PK) implies that u = v for all pairs {w,f} of vertices of G. The resolving set of G with the smallest cardility is called a basis of G. The dimemsion of G, denoted by dim(G), is the cardinality of a basis for G.Because of the interest application in chemistry, some scholars such as Harary, etc., devote to the investigation of the dimension of a graph G. In this subject, the problems to determine dimension for a graph and characterize its base are specially concerned. In [2]. Gray Chartrand gave a dimension bound for some graphs : dim(H) < dim(H x P2] < dirn(H) + 1. where H is a connected graph and P2 is a path of length 2. He also proved that both the upper and lower bounds are sharp.In our article, we first generalize the above bound for Pk: dim(H) < dim(H x Pk) < dirn(H) + 1. where H is a. connected graph and Pk is a path of length k.Additionally we prove both our upper and lower bound are sharp. We also characterize the bases for some graphs. At last, some other problems related to the dimensions of graphs arc considered.