若干圖的鄰點強可區(qū)別e-全染色.pdf

1、設G(V，E)是一個簡單圖，存在正整數(shù)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-鄰點強可區(qū)別E-全染色，簡記為k-E-AVSDTC.稱xeast(G)=min{k|G所有k-鄰點強可區(qū)別E-全染色

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