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

1、圖理論是一門非常年輕的學(xué)科，但是成熟很快．它是一種能在各種科學(xué)領(lǐng)域像計(jì)算機(jī)科學(xué)，物理，生物，化學(xué)，戰(zhàn)略學(xué)等學(xué)科中應(yīng)用的模型．圖染色問題是圖研究中的主要領(lǐng)域之一． 頻率分配問題(The Frequency Assignment Problem(FAP))是集中在點(diǎn)對點(diǎn)通訊問題中的一個(gè)一般的結(jié)構(gòu)，例如無線電通信和移動電話網(wǎng)絡(luò)．它要求用來傳播的頻率或頻道之間的干擾保持在一個(gè)可接受的水平，進(jìn)而有效地使用這些可用頻率．在此問題中，我們需要

2、給中轉(zhuǎn)站分配頻率波段．為了避免干擾，如果兩個(gè)站點(diǎn)離得非常近，那么它們的頻率至少要相差2.而且，如果兩個(gè)站點(diǎn)離得近(不是非常近)，那么它們得到的頻率不同．受到這個(gè)問題的啟發(fā)，Griggs和Yeh[10]引入了L(2，1)—標(biāo)號．2000年，G．J．Chang等人[11]把它推廣到了L(p，1)—標(biāo)號．圖G的L(p，1)—標(biāo)號是對G的頂點(diǎn)集的—個(gè)整數(shù)分配使得：若dG(u，v)=1，則|L(u)— L(v)|≥p；若dG(u，v)=2，則|L

3、(u)— L(v)|≥1. 這個(gè)標(biāo)號在一些文章中已經(jīng)研究過了，[11]中研究了弦圖，Whittesey等人在[12]中研究了G的剖分圖的L(2，1)—標(biāo)號．G的剖分圖si(G)是由G的每條邊上插入—個(gè)點(diǎn)所得到的圖．s1(G)的L(p，1)—標(biāo)號對應(yīng)于在原圖G上的(p，1)—全標(biāo)號[13]：設(shè)p是一個(gè)非負(fù)整數(shù)，圖G的一個(gè)k—(p，1)—全標(biāo)號是一個(gè)映射f：V(G)U E(G)→{0，1，…，k}使得： (1)G的任兩個(gè)相鄰

4、的頂點(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)u和邊e，有|f(u)— f(e)|≥p．我們稱這樣的一個(gè)分配叫G的(p，1)—全標(biāo)號．(p，1)—全標(biāo)號的跨度是指兩個(gè)標(biāo)號差中的最大值．G的(p，1)—全標(biāo)號的最小跨度叫(p，1)—全標(biāo)號數(shù)，記作λTp(G)．它是一種加強(qiáng)了條件的全染色，這個(gè)額外的條件是關(guān)聯(lián)的點(diǎn)和邊的標(biāo)號至少要相差

5、p． 注意到(1，1)—全標(biāo)號就是全染色，有λT1=XT-1，其中XT是全色數(shù)． 在文獻(xiàn)[22]中給出了下述定義： 定義1[22]G=(V(G)，E(G))，d是一個(gè)正整數(shù)，X是V(G)的—個(gè)子集，如果X中任意兩個(gè)點(diǎn)的距離都大于d，則稱X是d—寬度箱，d叫做X的寬度．顯然，d—寬度箱也是(d-1)—寬度箱，(d—2)—寬度箱等等． 定義2[22]給定圖G=(V(G)，E(G))，使得V(G)=k∪i=1X

6、i，且Xi(i=1…k)是V(G)的寬度兩兩不同的i—寬度箱的最小整數(shù)k叫圖G的泛寬度色數(shù)，記作Xp(G)．圖G的一個(gè)大小為Xp(G)的染色叫Xp(G)—染色．顯然，此處我們的目的是最小化k，可以假設(shè)對每個(gè)i，Xi是一個(gè)i—寬度箱， 泛寬度染色要求把所有的頂點(diǎn)剖分成寬度兩兩不同的i—寬度箱Xi，即同一寬度箱Xi中任兩點(diǎn)的距離大于i，Xi中的頂點(diǎn)要求使用同一種顏色． 本文我們得到了如下的結(jié)論； 定義2.1.1[26

7、]B={B1，B2，…，Bn}是一個(gè)集族．我們稱n個(gè)頂點(diǎn)的圖X(B)=(V，E)為B的交圖：V(X(B))={Vi|i=1，2，…，n)，E(X(B))={vivi|()i，j=1，2，…，n；Bi∩Bj≠φ．}． 設(shè)Zn={1，2，…，n}，其冪集為Z={Z1，Z2，…，Z2n|()i，Zi∈Zn}．我們考慮由集族Z'=Z—φ構(gòu)成的交圖X(Z’)的(p，1)—全標(biāo)號． 定理2.1.1交圖X(Z')如上所述，則

8、定理2.1.2若Kn，m(m＞n≥1)為完全二部圖，且△＞p，則(1)n=1，m≥2時(shí)，λTp(Kn，m)=m+p-1.(2)n≥2，m＞n時(shí)，(i)若滿足m—≥2p-1，則λTp(Kn，m)=m+p-1.(ii)若滿足m—n≥p且m—n＜2p-1，則λTp(Kn，m)=m+p． 引理2.2.1[20]若G滿足λT2(G)=△(G)+1且f是一個(gè)(△(G)+1)—(2，1)—全標(biāo)號：V(G)∪E(G)→{0，1，2，…，△(G)

9、+1}，則每個(gè)最大度點(diǎn)v，有f(v)=0或f(v)=△(G)+1. 引理2.2.2若G滿足λTp(G)=A(G)+p-1且f是一個(gè)(△(G)+p-1)—(p，1)—全標(biāo)號：V(G)∪E(G)→{0，1，2，…，A(G)+p-1}，則每個(gè)最大度點(diǎn)v，有f(v)=0或f(v)=△(G)+p-1. 定理2.2.3△＞p，如果圖G含有一個(gè)最大度點(diǎn)v相鄰于至少d(v)—p+1個(gè)最大度點(diǎn)，且最大度點(diǎn)的生成子圖不含三角形，那么λTp(

10、G)≥△+p． 定義2.2.1 G為簡單圖，V(G)={v1，V2，…，Vn}，把m個(gè)G的頂點(diǎn)vjo∈G(jo∈{1，2，…，n})連成圈，所得到的新圖，記為Cm·G(vjo)，簡記為G*．Gi(i=1，2，…，m)為G的m個(gè)復(fù)制圖，即新圖G*的點(diǎn)集和邊集為： 定理2.2.4 G的最大度為A(G)，且λTp(G)=△(G)+p-1，取vjo為G的任一最大度點(diǎn)，不妨記為V1，由定義2.2.1得到的新圖記為Cm·G(v1)，

11、簡記為G*1.則 定理2.2.5取G滿足：G的(p，1)—全標(biāo)號數(shù)為0≤λTp(G)≤2p-1，設(shè)f是G一個(gè)(p，1)—全標(biāo)號：f：V(G)UE(G)→[0，1，…，λTp(G)]，存在v0∈V(G)使得f(v0)=0，取vjo為v0，不妨記為v1，由定義2.2.1得到的圖記為Cm·G(v1)，簡記為G*2設(shè)G中與v1相鄰的邊的最大標(biāo)號為p+α(1≤α≤λTp(G)—p)，則m為偶數(shù)時(shí)，m為奇數(shù)時(shí)， 定義2.2.2 T為

12、樹，|T|=m，V(T)=．{u1，V2，…，um}，且T中除葉子外，其余點(diǎn)所有點(diǎn)的度數(shù)相等，△(T)=△．設(shè)G是一個(gè)n階圖，V(G)={v1，V2，…，Vn}，若G的(p，1)—全標(biāo)號數(shù)為λTp(G)，G中存在△(△≥2)個(gè)標(biāo)號相同的點(diǎn)V1，V，…，V△，其標(biāo)號設(shè)為α0(0≤α0≤λTp(G))，且與每個(gè)vi(i=1，2，…，△)相鄰的所有邊的標(biāo)號均小于與其相鄰的vi的標(biāo)號． 作G的m個(gè)復(fù)制圖G1，G2，…，Gm，用Gi(i=

13、1，2，…，m)代替ui(i=1，2，…，m)，當(dāng)Gi，Gj對應(yīng)的T中的點(diǎn)ui，uj相鄰時(shí)，把Gi中某個(gè)標(biāo)號為α0的點(diǎn)與Gj中某個(gè)標(biāo)號為α0的點(diǎn)連接起來，且Gi(i=1，2，…，m)中標(biāo)號為α0的點(diǎn)只能與Cj(j≠i)中一個(gè)標(biāo)號為α0的點(diǎn)相鄰，G中其余點(diǎn)的連邊方式不變．這樣所得到的圖記為T·G(v1，V2，…，v△)，簡記為G'T． 定理2.2.6G'T如上所述，則λTp(G)≤λTp(G'T)≤λTp(G)+2. 把定

14、義2.2.2中的G的△個(gè)標(biāo)號相同的點(diǎn)V1，V2，…，VA，其條件改為對()vi(i=1'2，…，△)，其鄰邊中至少有一條邊e的標(biāo)號大于與其相鄰的vi的標(biāo)號，與所有V1，v2，…，v△相鄰的邊中最大標(biāo)號為p+α(0≤α≤λTp(G)—p)． 按照定義2.2.2中的構(gòu)造方式構(gòu)造新圖，這樣所得到的圖記為T—G(v1，V2，…，v△)，簡記為G"T． 定義2.3.1[25，51]對兩個(gè)圖G和H，笛卡爾乘積圖G□H定義如下：V(G

15、□H)=V(G)×V(H)；E(G□H)={(u，v)(u’v')|v=v'且uu'∈E(G)或u=u’且vv'∈E(H)}． 定理2.3.1 Pm為長為m的路，V(Pm)={u1，u2，…，um，um+1}．H滿足；|H|=n，V(H)={v1，V2，…，Vn)，H的(p，1)—全標(biāo)號數(shù)為λTp(H)，且存在點(diǎn)v，其鄰邊中至少有一條邊的標(biāo)號大于v的標(biāo)號，設(shè)所有邊中的最大標(biāo)號為p+α(α≥0)，作Pm與H的笛卡爾積Pm□H，V(

16、Pm□H)={(ui，vj)|i=1，2，…，m+1；j=1，2，…，n)} 定義3.1.1[51]G是一個(gè)簡單圖，V(G)=．[v1，V2，…，vn}，I2是兩個(gè)點(diǎn)的獨(dú)立集，G[I2]是用I2代替G的每個(gè)頂點(diǎn)所得到的圖．G[I2]的點(diǎn)集和邊集如下：V(G[I2])={v1，v2，…，vn，v'1，v'2，…，V'n}，E(G[I2])=E(G)∪{v'iv'j，v'ivj|vivj∈E(G)}．G[I2]稱為G的點(diǎn)分裂圖．

17、 定義3.2.1[36]給定m個(gè)圖G0，G1，…，Gm-1，對i=0，1，…，m-1，令ei=vivi+1∈Gi，令cm=c0c1…Cm-1為長是m的圈，構(gòu)造新圖： (1)刪去ei，i=0，1，…，m-1. (2)合并所有的vi成—個(gè)點(diǎn)x． (3)將vi+1與ci合成—個(gè)點(diǎn)，i=0，1，…，m-1(i+1取模m)．令此圖為S1(G0，e0，G1，e1，…，Gm-1，em-1)，簡記為S1. 若給定m個(gè)