The Study On The Edge Metric Dimension Problem Based On Genetic Algorithms

Let G=(V,E)be a simple graph.A vertex v is said to distinguish edges e1 and e2 of G if d(e1,v)＝d(e2,v),where d(e1,v)and d(e2,v)represent the distances between vertex v and edges e1,e2 respectively.A subset S of V is called an edge metric generator of G,if there exists a vertex v∈S such that for any two edges e1 and e2 of G,v distinguishes e1 and e2.The cardinality of the edge metric generator with the least elements is called the edge metric dimension of G.The problem of edge metric dimension is an important issue in graph theory and combinatorial optimization.It was proposed by A.Kelenc and N.Tratnik and others in 2016.The problem of edge metric dimension of graphs has aroused researchers’ great interest and till now a great deal of results have been obtained.In this thesis,we present the genetic algorithm for the edge metric dimension problem and apply this algorithm to several kinds of graphs to get bounds for their edge metric dimensions respectively.