圖的(p,1_)全標(biāo)號及圖的弱鄰點(diǎn)可區(qū)分的染色問題.pdf

1、圖理論是一門非常年輕的學(xué)科，在許多的科學(xué)領(lǐng)域都有著廣泛的應(yīng)用背景．圖的染色問題是圖理論的一個重要組成部分，而且許多經(jīng)典的染色問題諸如點(diǎn)染色和邊染色等都已經(jīng)有了深入的研究。隨著科技的進(jìn)步，在各種新的科技問題的背景之下，許多新的染色問題也被相繼提出．
　　在無線電網(wǎng)絡(luò)中分配傳播的波段的問題時，產(chǎn)生了一個頻道分配問題．如果幾個站點(diǎn)是相鄰的，為了避免發(fā)射的信號相互干擾，那么在給這些相鄰的站點(diǎn)分配頻道時，它們得到的頻道相差至少為2；而且如果

2、兩個站點(diǎn)離得近(但不是非常近)，那么分配給它們的頻道也需要不同．如果把這個問題轉(zhuǎn)化成圖論的染色問題就是Griggs和Yeh提出的L(2,1)-標(biāo)號問題[4]．2000年，G．J．Chang等人把它推廣到圖的L(p,1)-標(biāo)號[5]．
　　圖G的L(p,1)-標(biāo)號是對G的頂點(diǎn)集的一個整數(shù)映射L，使得對任意的頂點(diǎn)u，v滿足：
　　(1)若dG(u，v)=1，則|L(u)-L(v)|≥p；
　　(2)若dG(u，v)=2，則

3、|L(u)-L(v)|≥1，(其中dG(u，v)表示u，v兩點(diǎn)之間的距離)．
　　一個圖G的關(guān)聯(lián)圖[6]是指把圖G的每一條邊用長為2的路代替．圖G的關(guān)聯(lián)圖的L(p,1)-標(biāo)號，是對G的一個特別的全染色，這種全染色就是由Havet和Yu提出的(p,1)-全標(biāo)號[7]：
　　設(shè)p是一個正整數(shù)，圖G的一個k-(p，1)-全標(biāo)號是一個映射f：V(G)∪E(G)→{0，1，…，k)，使得：
　　(1)G的任意兩個相鄰的頂點(diǎn)u，v

4、，有|f(u)-f(v)|≥1；
　　(2)G的任意兩條相鄰的邊e，e'，有|f(e)-f(e')|≥1；
　　(3)G的任意兩個關(guān)聯(lián)的點(diǎn)u和邊e，有|f(u)-f(e)|≥p．
　　我們稱這樣的一個標(biāo)號叫G的(p,1)-全標(biāo)號．(p，1)-全標(biāo)號的跨度是指標(biāo)號中的最大標(biāo)號與最小標(biāo)號的差．G的(p,1)-全標(biāo)號的最小跨度叫(p,1)-全標(biāo)號數(shù)，記作λT p(G)，即λTp(G)=min{k|G有一個k-(p,1)-全標(biāo)

5、}。
　　圖的鄰點(diǎn)可區(qū)分的邊染色(鄰強(qiáng)邊染色)[8]和鄰點(diǎn)可區(qū)分的全染色[9]是由張忠輔老師首先提出的，在數(shù)據(jù)傳輸問題上有一定的應(yīng)用背景，但是由于限制的條件比較強(qiáng)目前僅在樹，圈，完全圖等圖類上得到了解決。
　　在本文的第一章里,主要介紹了文章中所涉及的一些概念、術(shù)語和符號以及圖染色問題的發(fā)展情況.在第二章中,研究了圖的(p,1)-全標(biāo)號,給出了當(dāng)p=3,Δ≥9時,全標(biāo)號的一個上界和特殊圖的(p,1)-全標(biāo)號.第三章中研究了T