孫麗嬌，孫磊

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

1 引言

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

定義1.1[3]設(shè)p是一個(gè)非負(fù)整數(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，有|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.

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

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

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

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

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

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

定義1.3[4]對(duì)兩個(gè)圖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為簡(jiǎn)單圖，V(G)={v1,v2,…,vn}，把m個(gè)G的頂點(diǎn)vj0∈G(j0∈{1,2,…n})連成圈，所得到的新圖，記為Cm·G(vj0)，簡(jiǎn)記為G*.即Gi(i=1,2,…m)為G的m個(gè)復(fù)制圖，新圖G*的點(diǎn)集和邊集為：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

對(duì)?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的一個(gè)非正常(2,2,0)-(p,1)-全標(biāo)號(hào)，則標(biāo)號(hào)如下：首先對(duì)頂點(diǎn)標(biāo)號(hào)：當(dāng)i∈{1,2,…n}，令f(vi)=0.其次對(duì)邊標(biāo)號(hào)，當(dāng)i∈{1,2,…n-1}，令f(vivi+1)=p，f(vnv1)=p.至此完成Cn的一個(gè)非正常(2,2,0)-(p,1)-全標(biāo)號(hào).

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

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

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

參考文獻(xiàn)

[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)號(hào)[D].濟(jì)南：山東師范大學(xué)，2009.

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