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

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

2、兩個(gè)頂點(diǎn)的距離都大子d，稱X是一個(gè)寬度箱，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，這個(gè)整數(shù)k叫做圖G的泛寬度色數(shù)，記做Xp(G)．圖G的一個(gè)大小為Xp(G)的染色叫做Xp(G)—染色．顯然，此處我們的目的是最小化k．可以假設(shè)對(duì)每個(gè)i，

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

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

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

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

7、 [5]Fredeic Havet和Min—Li Yu給出了λTp(G)的上下界，提出了(p，1)—全標(biāo)號(hào)猜想：λTp(G)≤△(G)+2p-1.在本文中，我們主要得到如下結(jié)論： 定義2.1[38]設(shè)G表示任意一個(gè)連通圖，其中V(G)=．[v1，v2，…，vn}，G'表示G的一個(gè)復(fù)制圖，其中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設(shè)Pn表示一條階為n的路，則當(dāng)n＞5時(shí)，有xp(D(R))=5. 定理2.2設(shè)Wn表示一個(gè)輪，有Xp(D(Wn))=n+2. 定義3.1.1設(shè)G和G'表示任意兩個(gè)連通圖，其頂點(diǎn)集分別為：在G和G，之間疊加匹配uivi，vivi+1，vivi+2，…，vivi+m，…，uivi+(n-1)(i=1，2，

9、…，n；m=0，1，2，…，n-1；當(dāng)i+m＞n時(shí)，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設(shè)Pn表示一條階為n的路，有λT2(Pn(m+1)n，n)：△+2：m+5(m=0，1，2，…，n．—2，n≥4)． 定理3.1.2設(shè)Cn表示一個(gè)圈，有λT2(Cn(m=+1n，n))≥

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

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

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

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

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

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

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