Identifying And Locating Codes On Dihedrants

The dominating set theory of graph is one of the fastest developing fields in Graph Theory.It plays an important role in the fields of communication network,computer science,combinatorial optimization,coding theory and so on.Identifying and locating codes are two kinds of important codes closely related to the concept of dominating set of graph.They have important theoretical and practical significance in coding theory and real life.It is very difficult to determine the bounds of optimal r-verification code and -location code of graph,even for the simplest graph,cycle and path.In fact,this problem is NP-complete.Because the optimal bounds of the identifying and locating codes of graphs are NP-complete,the determination of the upper and lower bounds of these two codes and the characterization of extremum graphs are what many scholars want to study.This paper mainly studies the optimal bounds of the identifying and locating codes of some simple dihedrants.The main research contents are as follows: In the first part,the concepts of identification code,location code and dihedrant are given,and the research background and research progress at home and abroad are introduced.In the second part,We mainly study the optimal bounds of identifying and locating codes of partially connected 3-regular dihedrant,give the connectivity conditions and the optimal bounds of identifying and locating codes of 2-regular dihedrant,and the bounds of identifying and locating codes of 4-regular dihedrant are studied by establishing relations with circulant graph.In the third part,the connectivity conditions of partial 4-regular,6-regular and 8-regular dihedrants are given.By establishing the corresponding relationship between the vertices on partial 4-regular,6-regular and 8-regular dihedrants and the vertices in infinite square grid ,triangular grid and king grid respectively,using the known properties of verification code and location code in infinite square grid ,triangular grid and king grid ,the optimal bounds of identifying and location codes are studied.