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

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

2、兩個(gè)站點(diǎn)離得近(但不是非常近)，那么分配給它們的頻道也需要不同．如果把這個(gè)問(wèn)題轉(zhuǎn)化成圖論的染色問(wèn)題就是Griggs和Yeh提出的L(2,1)-標(biāo)號(hào)問(wèn)題[4]．2000年，G．J．Chang等人把它推廣到圖的L(p,1)-標(biāo)號(hào)[5]．
　　圖G的L(p,1)-標(biāo)號(hào)是對(duì)G的頂點(diǎn)集的一個(gè)整數(shù)映射L，使得對(duì)任意的頂點(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è)圖G的關(guān)聯(lián)圖[6]是指把圖G的每一條邊用長(zhǎng)為2的路代替．圖G的關(guān)聯(lián)圖的L(p,1)-標(biāo)號(hào)，是對(duì)G的一個(gè)特別的全染色，這種全染色就是由Havet和Yu提出的(p,1)-全標(biāo)號(hào)[7]：
　　設(shè)p是一個(gè)正整數(shù)，圖G的一個(gè)k-(p，1)-全標(biāo)號(hào)是一個(gè)映射f：V(G)∪E(G)→{0，1，…，k)，使得：
　　(1)G的任意兩個(gè)相鄰的頂點(diǎn)u，v

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

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