p~2阶非正规Cayley图的核

发布时间：2018-04-01 07:54

本文选题：图的核　切入点：Cayley图　出处：《云南师范大学》2017年硕士论文

【摘要】：图的核的研究是当前图论特别是代数图论中的一个前沿课题.一个图的核定义为与该图同态等价的最小阶的图.从理论上已经知道确定一般图的核是NP-完全问题,但由于图的核可以继承原图的许多重要性质,且结构相对原图较为简单,故对图的核的研究仍然具有重要的理论意义.由于确定一般图的核是NP-完全问题,因此在研究图的核相关问题时,通常需要对研究的图加一些限制条件,例如添加对称,顶点传递,边传递,正规性,或者Cayley图等条件.人们已经知道顶点传递图的核是顶点传递图,且顶点传递图的核的阶是原图的阶的因数,因此本工作就是围绕p~2阶(p是素数)的顶点传递图的核的研究展开的.本工作首先研究了 p~2阶的非正规Cayley的核.通过讨论p~2阶非正规图是否存在与其同态等价的诱导子图,来研究该图与其诱导子图的色数,团数和独立数之间的关系,进而确定两个图之间不存在同态,如果存在同态,则找出其同态映射.在此基础上确定出p~2阶非正规图的核.其次,本工作研究p~2阶对称循环图的核.2013年Rotheram研究了与交换群相对应的Cayley图的核的一些性质,本工作通过这些性质的进一步分析了研究了 p~2阶正规对称循环图的核的结构,进而确定了 p~2阶对称循环图的核。
[Abstract]:The study of the kernel of a graph is a frontier subject in graph theory, especially in algebraic graph theory. The kernel of a graph is defined as a graph of minimum order equivalent to the homomorphism of a graph. It is theoretically known that determining the kernel of a general graph is an NP-complete problem. However, since the kernel of a graph can inherit many important properties of the original graph, and the structure is relatively simple, the study of the kernel of the graph is still of great theoretical significance, since it is determined that the kernel of a general graph is a NP-complete problem. Therefore, in studying the kernel related problems of graphs, we usually need to add some restrictions to the graph, such as adding symmetry, vertex transitive, edge transitive, normality, etc. It has been known that the kernel of vertex transitive graph is vertex transitive graph, and the order of kernel of vertex transitive graph is the factor of the order of original graph. Therefore, this paper focuses on the study of the kernel of vertex transitive graphs of order p ~ 2 (p is prime). Firstly, we study the kernels of informal Cayley of order p2. By discussing whether there are inductive subgraphs equivalent to their homomorphism, we discuss the existence of subgraphs of order p ~ (2), which are equivalent to their homomorphism. In order to study the relationship between the chromatic number, the number of groups and the independent number of the graph and its induced subgraph, it is determined that there is no homomorphism between the two graphs, if there is a homomorphism, Then the homomorphic mapping is found. On this basis, the kernels of the irregular graphs of order p0 2 are determined. Secondly, the kernel of symmetric circulant graphs of order p0 2 is studied. In 2013, Rotheram studied some properties of the kernels of Cayley graphs corresponding to the abelian groups. In this paper, the kernel structure of normal symmetric cyclic graph of order p2 is studied by further analysis of these properties, and the kernel of symmetric cyclic graph of order p2 is determined.
【学位授予单位】：云南师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】