Goldberg snark圖的L(3，2，1)-標(biāo)號(hào)

董曉媛，馬登舉

(1.南通師范高等?？茖W(xué)校數(shù)理系，江蘇 南通 226000； 2.南通大學(xué)理學(xué)院，江蘇 南通 226007)

Goldberg snark圖的L(3，2，1)-標(biāo)號(hào)

董曉媛1，馬登舉2

(1.南通師范高等?？茖W(xué)校數(shù)理系，江蘇 南通 226000； 2.南通大學(xué)理學(xué)院，江蘇 南通 226007)

討論了Goldberg snark圖的L(3，2，1)-標(biāo)號(hào)問(wèn)題，給出了Goldberg snark圖Bk的L(3，2，1)-標(biāo)號(hào)數(shù)的界，即11≤λ3，2，1(Bk)≤16.

L(3，2，1)-標(biāo)號(hào)；Goldberg snark圖；標(biāo)號(hào)問(wèn)題

1 預(yù)備知識(shí)

頻率分配問(wèn)題是對(duì)每個(gè)無(wú)線電臺(tái)分配一個(gè)頻率，使得相互干擾的無(wú)線電發(fā)射臺(tái)所分配的頻率間隔在允許的范圍之內(nèi).Hale[1]于1980年將此問(wèn)題歸結(jié)為圖的T-染色問(wèn)題.Roberts于1990年研究了幾個(gè)不同地點(diǎn)的無(wú)線電發(fā)射臺(tái)如何有效分配無(wú)線電頻率問(wèn)題：將頻率用非負(fù)整數(shù)表示，從而相近的地點(diǎn)分配不同的頻率，且極相近的地點(diǎn)分配的頻率至少相差2，這樣使得這些頻率不會(huì)相互干擾.Chang等[2]于1996年更精確地提出了圖G的L(2，1)-標(biāo)號(hào)問(wèn)題.圖的L(3，2，1)-標(biāo)號(hào)是圖的L(2，1)-標(biāo)號(hào)的一個(gè)推廣.

一個(gè)圖G的L(3，2，1)-標(biāo)號(hào)是從圖G的頂點(diǎn)集到非負(fù)整數(shù)集的一個(gè)映射f：V(G)→{0，1，2，…}，使得對(duì)任意的兩個(gè)頂點(diǎn)u，v，|f(u)-f(v)|≥4-dist(u，v)，這里dist(u，v)表示u，v之間的距離.圖G的L(3，2，1)-標(biāo)號(hào)數(shù)是指最小的數(shù)k，使得G有一個(gè)k-L(3，2，1)-標(biāo)號(hào).圖G的L(3，2，1)-標(biāo)號(hào)數(shù)用λ3，2，1(G)表示.翟明清等[3]在2007年得到：對(duì)有最大度為Δ的任意圖G，λ3，2，1(G)≤Δ3+2Δ.

若一個(gè)3正則圖是二邊連通且不可3-邊著色的，同時(shí)圍長(zhǎng)至少為5，也無(wú)非平凡3-邊割集，則稱之為snark圖.Petersen圖是最小的snark圖，自1975年以來(lái)，更多的snark圖被研究人員發(fā)現(xiàn).本文對(duì)Goldberg snark圖的L(3，2，1)-標(biāo)號(hào)進(jìn)行研究.

圖1 Goldberg snark圖B3的一個(gè)畫法

圖2 的一個(gè)畫法

2 主要結(jié)論及證明

為了研究Goldberg snark圖的L(3，2，1)-標(biāo)號(hào)數(shù)，首先研究Goldberg圖Bk的L(3，2，1)-標(biāo)號(hào)數(shù).

引理1 當(dāng)k≡0(mod 4)時(shí)，有λ3，2，1(Bk)≤15.

圖3 的一個(gè)L(3，2，1)-標(biāo)號(hào)(豎線前即為)

引理2 當(dāng)k≡1(mod 4)時(shí)，有λ3，2，1(Bk)≤16.

圖4 的一個(gè)L(3，2，1)-標(biāo)號(hào)(豎線前面首位相連就是)

同理可以驗(yàn)證這是一個(gè)L(3，2，1)-標(biāo)號(hào)，從而λ3，2，1(Bk)≤16.

引理3 當(dāng)k≡2(mod 4)時(shí)，λ3，2，1(Bk)≤16.

圖5 的一個(gè)L(3，2，1)-標(biāo)號(hào)(豎線前面首位相連就是)

同理可以驗(yàn)證這是一個(gè)L(3，2，1)-標(biāo)號(hào)，從而λ3，2，1(B4m+2)≤16.

引理4 當(dāng)k≡3(mod 4)時(shí)，λ3，2，1(Bk)≤16.

圖6 的一個(gè)L(3，2，1)-標(biāo)號(hào)(豎線前面首位相連就是)

圖7 圖H

同理可以驗(yàn)證這是一個(gè)L(3，2，1)-標(biāo)號(hào)，故λ3，2，1(B4m+3)≤16.

由以上4個(gè)引理可知：

接下來(lái)給出λ3，2，1(Bk)的一個(gè)下界.

引理5 設(shè)圖H如圖7所示，則λ3，2，1(H)≥11.

假設(shè)λ3，2，1(H)≤10.設(shè)f是H的一個(gè)k-L(3，2，1)-標(biāo)號(hào)，則k≤10.

定理2 Goldberg snark圖Bk的L(3，2，1)-標(biāo)號(hào)數(shù)λ3，2，1(Bk)滿足

11≤λ3，2，1(Bk)≤16.

證明因?yàn)镠是Goldberg snark圖的一個(gè)子圖，所以λ3，2，1(Bk)≥11.再由定理1，λ3，2，1(Bk)≤16.因此11≤λ3，2，1(Bk)≤16.

[1] HALE W K. Frequency assignment：theory and application [J]. Proc IEEE，1980，68：1497-1514.

[2] CHANG G J，KUO D. TheL(2，1)-labeling on graphs [J]. SIAM J Discrete Math，1996(9)：309-316.

[3] 翟明清，董琳，呂長(zhǎng)虹.圖的L(3，2，1)-標(biāo)號(hào)[J].高校應(yīng)用數(shù)學(xué)學(xué)報(bào)A輯，2007，22(2)：240-246.

[4] CHIA M L，KUO D，LIAO H，et al.L(3，2，1) labeling of graphs[J].Taiwan J Math，1992，15：2439-2457.

[5] SHAO Z D，LIU J Z. TheL(3，2，1)-labeling problem on graphs[J].Math Appl，2004，17：596-602.

[6] HAO R X，NIU J Z，WANG X F，et al. A note on Berge-Fulkerson coloring[J].Discrete Mathematics，2009，309：4235-4240.

(責(zé)任編輯：李亞軍)

TheL(3，2，1)-labelingofGoldbergsnarkgraphs

DONG Xiao-yuan1，MA Deng-ju2

(1.Department of Mathematics and Physics，Nantong Normal College，Nantong 226000，China： 2.School of Sciences，Nantong University，Nantong 226007，China)

TheL(3，2，1)-labeling problem of a graph Goldberg snarkBkis considered. The bounds for theL(3，2，1)-labeling number of Goldberg snarkBkare given by 11≤λ3，2，1(Bk)≤16.

L(3，2，1)-labeling；Goldberg snark graph；the labeling problem

1000-1832(2017)03-0005-03

10.16163/j.cnki.22-1123/n.2017.03.002

2016-03-09

國(guó)家自然科學(xué)基金資助項(xiàng)目(11171114，11371207)；南通師范高等?？茖W(xué)校重點(diǎn)資助課題(TSGZ201606).

董曉媛(1984—)，女，碩士，講師，主要從事拓?fù)鋱D論研究；通信作者：馬登舉(1968—)，男，博士，副教授，主要從事拓?fù)鋱D論研究.

O 157.5 [學(xué)科代碼] 110·7470

A