The Study On The Metric Dimension And Relative Designs For The Graphs

The metric dimension was first introduced to graph theory independently in 1975 by Slater and in 1976 by Harary and Melter.The metric dimension of a graph is the minimum cardinality of a resolving set of .Since the parameter has appeared in many various areas including graph theory,pharmaceutical chemistry,biology,robot navigation,combinatorial optimization etc,it is important to study the metric dimension of a graph.In this thesis,we mainly study the metric dimension,the edge metric dimension,7)-metric dimension,and relative 2-design of the folded n-cube.In particular,we determine the exact value of the edge metric dimension of some graphs.The main results are as follows:1.We first introduce a new operation of vertices set.Using this new operation we give an equivalent condition for a subset of the folded n-cube to be resolving set.Then by explicitly constructing respectively minimal resolving sets for folded n-cube,where nis odd or even,we obtain upper bounds on the metric dimension of this graph.2.Using the combinatorial method we construct edge metric generators for foldedn-cube and prove that the edge metric generators are minimal.We get upper bounds on the edge metric dimension of this graph.Moreover,we find the edge metric dimensions of both convex polytopes and their related graphs.3.l-metric dimension is given by constructing l-resolving sets for folded n-cube.4.By using the theory of association schemes and relative t-designs,we explicitly compute the Fisher type lower bound for relative 2-designs on folded n-cube under certain conditions.