幾類圖的泛寬度染色和(p，1)-全標號.pdf

1、隨著圖論理論的發(fā)展，圖論分出許多分支，起源于150年前的四色猜想的染色問題有著極其重要的地位，并且在組合分析和實際生活中有著廣泛的應用．染色問題是圖論研究中一個很活躍的課題，得到了許多有趣而實用的結果，同時又拓展出一些新的分支．近年來，又提出了許多新的染色問題，這些染色問題在頻率分配中有很強的應用，如：泛寬度染色，(p，1)—全標號． 定義1[1]設G=(V(G)，E(G))，d是一個正整數(shù)，X是V(G)的一個子集，如果X中任意

2、兩個頂點的距離都大子d，稱X是一個寬度箱，d叫做X的寬度．顯然，d—寬度箱也是(d-1)—寬度箱、(d—2)—寬度箱等等． 定義2[1]給定圖G=(V(G)，E(G))，使得V(G)=X1∪X2∪…∪Xk(Xi(i=1，2，…，k)是V(G)的寬度兩兩不同的寬度箱)的最小整數(shù)k，這個整數(shù)k叫做圖G的泛寬度色數(shù)，記做Xp(G)．圖G的一個大小為Xp(G)的染色叫做Xp(G)—染色．顯然，此處我們的目的是最小化k．可以假設對每個i，

3、Xi是—個i—寬度箱． 圖的泛寬度染色是一種以距離為依據(jù)準則的圖頂點的剖分問題．對于不具有特定圖結構的任意圖來說，研究圖的泛寬度色數(shù)是非常困難的，而且目前已知的結論中，也都是針對具有具體圖結構的圖類來研究的，如：無限正方形[2]，完全圖Kn的剖分圖S(Kn)[1]的泛寬度色數(shù)，無限3—正則樹的泛寬度色數(shù)是7[3]．因此，在文獻[1]中作者猜想：確定任意圖的泛寬度色數(shù)是NP完備問題． 在頻率分配問題中，會有下面的情形出現(xiàn)：

4、我們需要給中轉站分配頻率波段(每個中轉站得到對應于一個整數(shù)的頻率波段)．為了避免干擾，如果兩個站點離得非常近，那么它們的頻率之差至少要相差2，而且，如果兩個站點離得近(不是非常近)，那么它們得到的頻率不同．受到這個問題的啟發(fā)，Gringgs和Yeh[4]引進了L(2，1)—標號，它的自然推廣是L(p，1)—標號， 定義3[5]設p是一個非負整數(shù)，圖G的一個L(p，1)一標號是從V(G)到一個整數(shù)集合的映射L，必須滿足：對于任意的

5、頂點u，v (1)若dG(u，v)=1，則|L(u)—L(v)|≥p； (2)若dG(u，v)=2，則|L(u)—L(v)|≥1. 特別地，Whittlesey等人在文獻[7]中研究了G的剖分圖S1(G)的L(p，1)—標號，G的剖分圖S1(G)是有圖G在每條邊上插入一個點所得到的圖，S1(G)的L(p，1)—標號對應與G的L(p，1)—全標號． 定義4[5]設p是一個非負整數(shù)，圖G的一個k—(p，1)—

6、全標號是一個映射f：V(G)∪E(G)→{0，1，2，…，k}，使得： (1)G的任意兩個相鄰的頂點u和v，有|f(u)—f(v)|≥1， (2)G的任意兩條相鄰的邊e和e'，有|f(e)—f(e')|≥1， (3)G的任意兩個相關聯(lián)的點v和邊e，有|f(v)—f(e)|≥p，(p，1)—全標號的跨度是指兩個標號差的最大值，圖G的(p，1)—全標號的最小跨度叫圖G的(p，1)—全標號數(shù)，記做λTp(G)．

7、 [5]Fredeic Havet和Min—Li Yu給出了λTp(G)的上下界，提出了(p，1)—全標號猜想：λTp(G)≤△(G)+2p-1.在本文中，我們主要得到如下結論： 定義2.1[38]設G表示任意一個連通圖，其中V(G)=．[v1，v2，…，vn}，G'表示G的一個復制圖，其中V(G’)={u1，u2，…，un)．在G和G'之間加匹配viui(i=1，2，…，n)，得到新圖D(G)，則V(D(G))=V(G)∪V(

8、G')，E(D(G))=E(G)∪E(G')∪{viui，i=1，2，…，n}，不妨稱D(G)為雙圖． 定理2.1設Pn表示一條階為n的路，則當n＞5時，有xp(D(R))=5. 定理2.2設Wn表示一個輪，有Xp(D(Wn))=n+2. 定義3.1.1設G和G'表示任意兩個連通圖，其頂點集分別為：在G和G，之間疊加匹配uivi，vivi+1，vivi+2，…，vivi+m，…，uivi+(n-1)(i=1，2，

9、…，n；m=0，1，2，…，n-1；當i+m＞n時，i+m為模n意義下的加法)．這樣得到一系列圖G(1)n，n，G(2)n，n，…，G(m=1)n，n，…，G(n)n，n稱為圖G和G'的弱聯(lián)圖．顯然G(n)n，n：G∨G． 定理3.1.1設Pn表示一條階為n的路，有λT2(Pn(m+1)n，n)：△+2：m+5(m=0，1，2，…，n．—2，n≥4)． 定理3.1.2設Cn表示一個圈，有λT2(Cn(m=+1n，n))≥

10、△+2=m+5(m=0，1，2，…，n-1)；當n為偶數(shù)時，λT2(C(m+1)n，n)=△+2=m+5(m=0，1，2，…，n-1)． 定義3.2.1[29]設G是一個簡單圖，V(G)={v1，V2，…，Vn}．I2是兩個點的獨立集，G[I2]是通過I2代替G的每個頂點后所得到的圖，即G的每個頂點vi都有一個復制點v'i，I2中每個點仍按對應點的連邊方式與其他點連邊．G[I2]的點集和邊集對應如下：則稱G[I2]為G的點分裂圖

11、． 定理3.2.1 Pn表示階為n的路，Pn[I2]表示路Pn的點分裂圖，則有 定理3.2.2Cn(n≥3)表示一個圈，Cn[I2]表示圈Cn的點分裂圖，則當n為偶數(shù)時，有λT2(Cn[I2])=6. 定理3.2.3 Kn[I2]表示完全圖Kn的點分裂圖，則有λT2(Kn[I2])≥2n． 定義3.3.1[12]設T(G)表示任意圖G的全圖，其頂點集對應于圖G的頂點和邊，全圖T(G)中兩個頂點是相鄰的，當

12、且僅當圖G中對應的頂點或邊相鄰，或者是對應的頂點和邊是相關聯(lián)的，不妨設圖G的頂點集V(G)={v1，v2，…，vn}，E(G)={e1，e2，…，em}，那么 E(T(G))={ViVj|vivj∈G}∪{eiej|ei和ej在G中相鄰}∪{viej|vi和ej在G中相關聯(lián)}． 定理3.3.1設T(Cn)表示圈Cn的全圖，則有λT2(T(Gn))≥6；特別地，當n為偶數(shù)時，有λT2(T(Cn))=6. 定理3.

13、3.2 Pn表示階為n的路，T(Pn)表示路Pn的全圖，則有 定理3.4.1設G表示一棵最大度△(G)=3的樹，并且G中所有的最大度點在一條路上，則有λT2(G)≤5. Fm表示階為m+1的扇，當n個扇Fm的扇心連成圈時，用Cn·F[27]m表示．設則對于圖Cn·F的(2，1)—全標號有下面的定理．定理3.4.2當n蘭0(mod2)時，有 在含有n個頂點的路Pn上，當且僅當兩點的距離(模)為k時加一條邊，所得到

14、的圖稱為pkn圖[21][39]．下面我們給出了部分pkn圖的(2，1)—全標號． 定理3.4.3對圖pkn，有λT2(Pkn)=6，k＞1，n≥3k+2. 在含有n個頂點的圈Cn上，當且僅當兩點的距離(模)為k時加一條邊，所得到的圖稱為Chn圖[22]，下面我們給出了圖C24m(m≥1)的(2，1)—全標號． 定理3.4.4λT2(C24m)=6，m≥1. 對于完全圖Kn，u，v∈V(Kn)，刪去邊uv

15、，其它點和邊不變，則得到了圖Kn— uv，下面我們給出了一類圖Kn— uv的(2，1)—全標號． 定理3.4.5當n為奇數(shù)且n≥3時，有λT2(Kn—uv)=n+1. 不妨設V(Cn)={v1，v2，…，vn}，V(Cn)的一個復制V'(Cn)記為{u1，u2，…，un}，在V(Cn)和其復制V'(Cn)之間疊加不同的匹配，就構成了一系列新圖：Sn，Sn1，M(Cn)．下面我們給出了這些圖的(，1)—全標號． 在

16、V(Cn)和V'(Cn)之間疊加匹配uivi(i=1，2，…，n)和vivi+1(i=1，2，…，n-1)，vnv1，得到圖Sn，有： 定理3.5.1當n為偶數(shù)時，有λTp(Sn)=△+p=p+4. 在Sn(n為偶數(shù))中，把Sn中所有ui(i=1，2，…，n)按u1u2，u2u3，…，un-1un，unu1的方式連成圈，得到圖Sn1，有：定理3.5.2當n為偶數(shù)時，有λTp(Sn1)=△+p=p+4. 我們稱由M