若干圖的鄰點(diǎn)強(qiáng)可區(qū)別e-全染色.pdf

1、設(shè)G(V，E)是一個(gè)簡(jiǎn)單圖，存在正整數(shù)k，如果映射f:E(G)∪ V(G)→{1，2,…，k}滿足:對(duì)(∨)uv∈E(G)，f(u)≠f(v)，f(v)≠f(uv)，f(u)≠f(uv).對(duì)(∨)uv∈E(G)，C(u)≠C(v)，其中C(u)={f(u)}∪{f(v)}∪{f(uv)|uv∈E(G)}.則稱f是圖G的k-鄰點(diǎn)強(qiáng)可區(qū)別E-全染色，簡(jiǎn)記為k-E-AVSDTC.稱xeast(G)=min{k|G所有k-鄰點(diǎn)強(qiáng)可區(qū)別E-全染色

2、}為圖G的鄰點(diǎn)強(qiáng)可區(qū)別E-全色數(shù).
　　本文利用色集分配法、反證法、組合分析法、構(gòu)造函數(shù)法，探討了若干直積圖、若干聯(lián)圖和冠圖、若干路、圈運(yùn)算圖的鄰點(diǎn)強(qiáng)可區(qū)別E-全染色問(wèn)題，并得到了相應(yīng)圖的鄰點(diǎn)強(qiáng)可區(qū)別E-全色數(shù)，最后運(yùn)用概率方法得到了圖的鄰點(diǎn)強(qiáng)可區(qū)別E-全色數(shù)的兩個(gè)界.
　　論文共分為五個(gè)部分:
　　第一部分介紹了本文所涉及的相關(guān)概念和已經(jīng)得到的一些結(jié)果.
　　第二部分討論了笛卡爾直積圖、強(qiáng)矢積圖、字典積、半強(qiáng)矢