论文部分内容阅读
设G(V，E)是一个简单图，存在正整数k，如果映射f:E(G)∪ V(G)→{1，2,…，k}满足:对(∨)uv∈E(G)，f(u)≠f(v)，f(v)≠f(uv)，f(u)≠f(uv).对(∨)uv∈E(G)，C(u)≠C(v)，其中C(u)={f(u)}∪{f(v)}∪{f(uv)|uv∈E(G)}.则称f是图G的k-邻点强可区别E-全染色，简记为k-E-AVSDTC.称xeast(G)=min{k|G所有k-邻点强可区别E-全染色}为图G的邻点强可区别E-全色数. 本文利用色集分配法、反证法、组合分析法、构造函数法，探讨了若干直积图、若干联图和冠图、若干路、圈运算图的邻点强可区别E-全染色问题，并得到了相应图的邻点强可区别E-全色数，最后运用概率方法得到了图的邻点强可区别E-全色数的两个界. 论文共分为五个部分: 第一部分介绍了本文所涉及的相关概念和已经得到的一些结果. 第二部分讨论了笛卡尔直积图、强矢积图、字典积、半强矢积图的邻点强可区别E-全染色，并给出了其相应的色数. 第三部分讨论了几类联图和冠图的邻点强可区别E-全染色，并给出了其相应的色数. 第四部分讨论了路、圈运算图的邻点强可区别E-全染色，并给出了其相应的色数. 第五部分运用概率方法研究了图邻点强可区别E-全色数的两个上界.