The Dimensions of Graphs and Constructions of Their Bases

IntroductionGraph G,considered in this paper,is finiteand simple with vertex set V ( G) and edge setE( G) .Let d( x,y) denote the distance between xand y in G and W={w1,w2 ,…,wk}denote the or-dered set of V( G) .For any given v∈V( G) ,therepresentation of v with respect to W is the k- vec-tor:r( v| W) ={d( v,w1) ,d( v,w2 ) ,…,d( v,wk) }.The ordered set W is called a resolving set of G ifr( u| W) =r( v| W) implies that u=v for all pairs{u,v}of vertices of G. A resolving set of G with…

The Dimensions of Graphs and Constructions of Their Bases

Let G= (V,E) be a connected graph and W = {w1 ,w1,… ,wk } an ordered set of V. Given v ∈ V, the repsolving set of G if r(u|W)=r(v|W) implies that u=v for all pairs {u,v} of vertices of G. The resolving set of G with the smallest cardinality is called a basis of G. The dimension of G, dim (G), is the cardinality of a basis for G. The bound of a Cartesian product of a connected graph H and a path Pk was reached: dim(H)≤dim (H × Pk)≤dim (H)+1. Then, the dimension value of some graphs was given. At last, the constructions of some graphs'bases were showed.