Study On Metric Dimension Of Some Graphs

The metric dimension,edge metric dimension and mixed metric dimension are the important problems in the fields of graph theory and optimization.The metric dimension problem of graphs is widely used in comb_inatorial optimization,isomorphism of graphs,pharmaceutical chemistry,robot navigation,image processing and telecommunications,and it is NP-hard to solve the metric dimension,edge metric dimension and mixed metric dimension of graphs.Therefore,it is significant to study the metric dimension of graphs.Plane graph T_n is a simple connected graph with a vertex set of V(T_n)=?x_i,y_i,z_i|1?i?n} and an edge set of E(T_n)=?x_ix_i+1;y_iy_i+1|1?i?n} U {x_iy_i;y_iz_i;x_i+1y_i;y_i+1z_i|1?i?n?.Plane graph B_n is a simple connected graph with a vertex set of V(B_n)=?a_i;b_i;c_i;di;e_i|1?i?n} and an edge set of E(B_n)={a_ia_i+1;b_ib_i+1;didi+1;e_ie_i+1|1?i?n}(?){a_ib_i;b_ic_i;b_i+1c_i;c_idi;die_i|1?i?n}.In this thesis,we study the edge metric dimension and the mixed metric dimension of plane graphs T_n and B_n.The results are as follows:1.With respect to the edge metric dimension of the plane graph T_n,when 3?n?6,the edge metric dimension of the plane graph T_n is obtained by constructing and calculating.Whenn?7,the edge metric generator is constructed according to four cases:n?0,1,2,3(mod 4)and the metric representation of each edge with respect to these four sets of vertices is calculated,respectively.Using the proof by contradiction we prove that these sets of vertices are the edge metric basis of the plane graph T_n and then we obtain the edge metric dimension of T_n.The detailed results are as follows:With respect to the mixed metric dimension of the plane graph T_n,when 3?n?4,the mixed metric dimension of the plane graph T_n is obta_ined by constructing and calculating.When n?5,the mixed metric generator is constructed according to four cases:n?0,1,2,3(mod 4)and the metric representation of each element with respect to these four sets of vertices is calculated,respectively.Using the proof by contradiction we prove that these sets of vertices are the mixed metric basis of the plane graph T_n and then we obtain the mixed metric dimension of T_n.The deta_iled results are as follows:2.With respect to the edge metric dimension of the plane graph B_n,when n?3,an edge metric generator of the plane graph B_n is constructed according to the parity of n and the metric representation of each edge with respect to these sets of vertices is calculated,respectively.Using the proof by contradiction we prove that these sets of vertices are the edge metric basis of the plane graph B_n and then we obtain the edge metric dimension of B_n.The resulting edge metric dimension is dim_e(B_n)=4.With respect to the mixed metric dimension of the plane graph B_n,when 3?n?5,the mixed metric dimension of the plane graph B_n is obta_ined by constructing and calculating.When n? 6,a mixed metric generator of the plane graph B_n is constructed according to the parity of n and the metric representation of each element with respect to these sets of vertices is calculated,respectively.Using the proof by contradiction and the edge metric dimension we prove that these sets of vertices are the mixed metric basis of the plane graph B_n and then we obtain the mixed metric dimension of B_n.The detailed results are as follows:...