| The study of cores of different types of graphs is currently a relatively new and an active topic in graph theory,in particular,in algebraic graph theory.The core of a graph is defined to be a graph which is homomorphism equivalent to the original graph and which has the smallest order.It is well known that determining the cores of general graphs is a NP-complete problem.As the core of a graph can inherit many important properties of the original graph and the structure of the core is relatively simple,so the research on cores of graphs still has important theoretical significance.Since determine the cores of general graphs is a NP-complete problem,therefore in practice,additional restrictions are usually added to the specific graph,such as symmetry,vertex-transitivity,edge-transitivity,normality,or Cayley graph restriction.It is already known that the core of a vertex-transitive graph is vertex-transitive and the order of the core of a vertex-transitive graph is a divisor of the order of the original graph.Therefore,the content of this thesis goes around the cores of vertex-transitive graphs of order p~2(p is prime).In this thesis,we first study the cores of non-normal Cayley graphs of order p~2.Our study is mainly based on investigating the relationship between the chromatic numbers,clique numbers and independence numbers of the associated graphs and their induced subgraphs,then determining that there is no homomorphism equivalent to the given graph.Based on this,we determine the cores of all non-normal Cayley Graphs of order p~2.Second,we study the cores of symmetric circulant graphs of order p~2.In 2013,Rother-am studied some properties of the cores of Cayley graphs detemined by abelian group.In this thesis,using the properties of cores of the Cayley graphs detemined by abelian group,we analysis the core of regular symmetric circulant graph of order p~2,and then determine the core of symmetric circulant graph of order p~2. |
