本文選題：圖的核　切入點：Cayley圖　出處：《云南師范大學(xué)》2017年碩士論文

【摘要】：圖的核的研究是當(dāng)前圖論特別是代數(shù)圖論中的一個前沿課題.一個圖的核定義為與該圖同態(tài)等價的最小階的圖.從理論上已經(jīng)知道確定一般圖的核是NP-完全問題,但由于圖的核可以繼承原圖的許多重要性質(zhì),且結(jié)構(gòu)相對原圖較為簡單,故對圖的核的研究仍然具有重要的理論意義.由于確定一般圖的核是NP-完全問題,因此在研究圖的核相關(guān)問題時,通常需要對研究的圖加一些限制條件,例如添加對稱,頂點傳遞,邊傳遞,正規(guī)性,或者Cayley圖等條件.人們已經(jīng)知道頂點傳遞圖的核是頂點傳遞圖,且頂點傳遞圖的核的階是原圖的階的因數(shù),因此本工作就是圍繞p~2階(p是素數(shù))的頂點傳遞圖的核的研究展開的.本工作首先研究了 p~2階的非正規(guī)Cayley的核.通過討論p~2階非正規(guī)圖是否存在與其同態(tài)等價的誘導(dǎo)子圖,來研究該圖與其誘導(dǎo)子圖的色數(shù),團數(shù)和獨立數(shù)之間的關(guān)系,進(jìn)而確定兩個圖之間不存在同態(tài),如果存在同態(tài),則找出其同態(tài)映射.在此基礎(chǔ)上確定出p~2階非正規(guī)圖的核.其次,本工作研究p~2階對稱循環(huán)圖的核.2013年Rotheram研究了與交換群相對應(yīng)的Cayley圖的核的一些性質(zhì),本工作通過這些性質(zhì)的進(jìn)一步分析了研究了 p~2階正規(guī)對稱循環(huán)圖的核的結(jié)構(gòu),進(jìn)而確定了 p~2階對稱循環(huán)圖的核。
[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.
【學(xué)位授予單位】：云南師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前7條

1 陳進(jìn)之;論頂點傳遞圖[J];益陽師專學(xué)報;1987年06期

2 王迪吉;商Cayley圖與頂點傳遞圖[J];新疆師范大學(xué)學(xué)報(自然科學(xué)版);1999年01期

3 屠伯X，

本文編號：1694627