Some Research On The Structural Properties Of Trace Graphs And Their Random Graphs

This thesis mainly studies the structural properties of two kinds of graphs:one is trace graphs,the other is complement of paths and square of paths.For the trace graphs part,we consider the number of cliques,as well as the degree distribution of their random graphs.Regarding complement of paths and square of paths,we mainly study their near automorphisms.There are four chapters in this thesis.The first chapter is an introduction,which introduces the research background and significance,research status,main results,and basic definitions and descriptions of symbols.In Chapter two,we study some structural properties of trace graphs and their random graphs.Firstly,we define basic-numbers and use it as a tool to characterize the maximum clique of trace graphs defined over the real number field R.Secondly,we give an upper bound on the clique number of trace graphs defined over a finite field Fq.Finally,we define the random graphs of the trace graphs,using probabilistic methods,we obtain the degree and average distance of the trace graphs defined on the secondorder field F,and on this basis,the degree distribution of their random graphs are obtained.In Chapter three,we study the near automorphism of complement or square of paths.Let Pn is a path of npoints,Pn and Pn2 is complement of paths and square of paths,respectively.First,we completely characterize all near automorphisms that satisfy π(Pn)=2 when n≥5.Secondly,we prove that when n≥6,π(Pn2)=2[(n-3)/2]and characterize all near automorphisms when the equal sign holds.The fourth chapter is conclusions and prospects of this thesis.We summarize the main results of this thesis and introduce further research issues.There are 3 figures and 84 references in this article.