论文部分内容阅读
设G是具有顶点集V(G)和边集五(G)的无向有限简单图，称G的一个正常全染色是G的Smarandachely邻点全染色，若对VuvεE(G),都有|C(u)C(v)|≥1且|C(v)C(u)|≥1,其中C(u)是对点u所着的颜色和与其关联边所着的颜色组成的集合.把染色方法中所用的最少颜色数称为G的Smarandachely邻点全色数，记为xsat(G). 本文根据图的结构性质，主要利用结构拼凑法，构造染色函数法和穷举法，研究了几类冠图和两类联图，两类k重Mycielski图，二种积图(强矢积图、半强矢积图、字典积图)以及两类3-正则图的Smarandachely邻点全染色，得到了这些图的Smarandachely邻点全色数，进一步验证了这些图对Smarandachely邻点全染色猜想都成立. 论文共分为五部分： 第一部分主要介绍了一些本文所用到的基本概念和符号. 第二部分主要研究了几类冠图和联图的Smarandachely邻点全染色问题，并给出这些图的Smarandachely邻点全色数. 第三部分主要讨论了两类k重Mycielski图的Smarandachely邻点全染色问题，并给出其Smarandachely邻点全色数. 第四部分主要研究了由圈与路、圈运算成的三种积图的Smarandachely邻点全染色问题,并给出其Smarandachely邻点全色数. 第五部分构造了两类3-正则图Rkm和G(V,E),给出了其对应的Smarandachely邻点全色数，同时验证了这两类3-正则图满足Smarandachely邻点全染色猜想.