孫麗嬌，孫磊

(山東師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山東 濟南 250014)

1 引言

在頻率分配問題中，假如給定一些基站，為避免干擾，需給每個基站分配一個整數(shù)的頻率波段，要求非常近的基站間必須是至少差2個頻道的，稍近的一些基站分配不同的頻道.受到這個問題的啟發(fā)，Griggs和Yeh[1]引入了L(2,1)-標(biāo)號，它的自然推廣就是圖G的L(p,1)-標(biāo)號.在此問題中，若某些中轉(zhuǎn)站不受控制或是已壞掉，則反映到標(biāo)號問題中，即可允許某些頂點標(biāo)號不受限制.Whittlesey等人在文獻[2]中研究了G的剖分圖的L(2,1)-標(biāo)號，G的剖分圖S1(G)是由圖G在每條邊上插入一個點所得到的圖.S1(G)的L(p,1)-標(biāo)號對應(yīng)于G的L(p,1)-全標(biāo)號.自然地，有如下定義：

定義1.1[3]設(shè)p是一個非負(fù)整數(shù)，圖G的一個k-(p,1)-全標(biāo)號是一個映射f:V(G)∪E(G)→{0,1,…k}，使得：

(1)G的任意兩個相鄰的頂點u和v，有|f(u)-f(v)|≥1；

(2)G的任意兩條相鄰的邊e和e′，有|f(e)-f(e′)|≥1；

(3)G的任意兩個關(guān)聯(lián)的點u和邊e，有|f(u)-f(e)|≥p.

定義1.2 設(shè)p,r,s,t是非負(fù)整數(shù)，圖G的一個非正常(r,s,t)-(p,1)-全標(biāo)號是一個映射f:V(G)∪E(G)→{0,1,2,…k}，使得：

(1) G的任意兩個相鄰的頂點u和v，對?u∈V(G),其鄰接頂點中除至多r個點外，有|f(u)-f(v)|≥1；

(2) G的任意兩條相鄰的邊e和e′，對每一e∈E(G),其鄰接邊中除至多s條邊外，有|f(e)-f(e′)|≥1；

(3) G的任意兩個相鄰的邊e和頂點v，對每一頂點v∈V(G)，其關(guān)聯(lián)邊中除至多t條邊外，均有|f(e)-f(v)|≥p；對每一條邊e∈E(G)，其關(guān)聯(lián)點中除至多(t≤2)個頂點外，均有|f(e)-f(v)|≥p.

對任兩相鄰頂點u和v，若f(u)=f(v)，則稱u和v為一對壞點.

對任兩條相鄰邊e和e′，若f(e)=f(e′)，則稱e和e′為一對壞邊.

定義1.3[4]對兩個圖G和H，笛卡爾乘積圖G□H定義如下：

V(G□H)=V(G)×V(H),

E(G□H)={(u,v)(u′,v′)|v=v′且uu′∈E(G)或u=u′且vv′∈E(H)}.

定義1.4[5]G為簡單圖，V(G)={v1,v2,…,vn}，把m個G的頂點vj0∈G(j0∈{1,2,…n})連成圈，所得到的新圖，記為Cm·G(vj0)，簡記為G*.即Gi(i=1,2,…m)為G的m個復(fù)制圖，新圖G*的點集和邊集為：

定義1.5[5]Cn是一個圈，設(shè)V(Cn)={v1,v2,…,vn}，V(Cn)的一個復(fù)制記為{u1,u2,…,un}.定義新圖Sn的頂點集和邊集如下：

V(Sn)={v1,v2,…,vn,u1,u2,…,un}；

E(Sn)=E(Cn)∪ {uivi,i=1,2,…n}∪ {unv1,u1v2,…un-1vn}.

本文未加說明的定義及標(biāo)記參見參考文獻[6].

2 主要結(jié)果及其證明

首先給Pm□H中的頂點標(biāo)號：當(dāng)i∈{1,2,…m+1}時，對?(ui,vj)∈V(Pm□H)，令f*(ui,vj)=f(vj)+1(j=1,2,…n).

其次對Pm□H中的邊標(biāo)號：先給邊(ui,vk)(ui,vl)標(biāo)號，令：

f*((ui,vk)(ui,vl))=f(vkvl)+1(i=1,2,…m+1;k,l=1,2,…n且k≠l)；

其次對邊(uk,vj)(ul,vj)標(biāo)號(k,l=1,2,…m+1且k≠l,j=1,2,…n)，分情況討論：

(1)若在H中存在vj鄰邊e，使f(vj)

(2)若在H中，vj的鄰邊標(biāo)號均比vj的標(biāo)號小，則令f*((uk,vj)(ul,vj))=0.

易證f*是Pm□H的一個非正常(2,2,0)-(p,1)-全標(biāo)號.

證明：v1為G中一最大度點，由引理知，f(v1)=0或f(v1)=Δ(G)+p-1，不失一般性，可設(shè)v1在原圖G中的標(biāo)號為Δ(G)+p-1.

對?vi1，令f*(vi1)=Δ(G)+p(i=1,2,…m)；

對?vi1vi+1,1(i=1,2,…m-1)，令f*(vi1vi+1,1)=Δ(G)且f*(vm1v1,1)=Δ(G)；

證明：可設(shè)V(Cn)={v1,v2,…,vn}，f為Cn的一個非正常(2,2,0)-(p,1)-全標(biāo)號，則標(biāo)號如下：首先對頂點標(biāo)號：當(dāng)i∈{1,2,…n}，令f(vi)=0.其次對邊標(biāo)號，當(dāng)i∈{1,2,…n-1}，令f(vivi+1)=p，f(vnv1)=p.至此完成Cn的一個非正常(2,2,0)-(p,1)-全標(biāo)號.

證明：下面給出Sn的一個非正常(2,2,0)-(p,1)-全標(biāo)號f:V(Sn)∪E(Sn)→{0,1,2,…p+1}；

其中對Sn中頂點標(biāo)號，當(dāng)i∈{1,2,…n}，令f(vi)=0,f(ui)=1；對Sn中邊標(biāo)號，當(dāng)i∈{1,2,…n-1}時，令f(vivi+1)=p，f(vnv1)=p，f(uivi+1)=p+1，f(unv1)=p+1.當(dāng)i∈{1,2,…n}時，令f(uivi)=p+1.

易證f為Sn的一個非正常(2,2,0)-(p,1)-全標(biāo)號.

參考文獻

[1]Griggs J R, Yeh R K. Labeling graph with a condition at distance two[J].SIAM J Discrete Math,1992,5(4):586-595.

[2]Whittles M A, Georges J P, M auro D W.O n theλ-number ofQnand related graphs [J].SIAM J.Discrete Math,1995,8(4):499-506.

[3]F.Havet,M.-L.Yu.(p,1)-Total labeling of graphs[J].Discrete Math,2008,308:496-513.

[4]Sandi Klavzar.Coloring graph Products-A survey[J].Discrete Math,1996,155:135-145.

[5]張珊珊.圖的泛寬度染色和(p,1)-全標(biāo)號[D].濟南：山東師范大學(xué)，2009.

[6]BOLLOBAS B. Modern Graph Theory [M].NewYork:Springer-Verlag,1998.