Goldberg snark圖的L(3，2，1)-標號

董曉媛，馬登舉

(1.南通師范高等專科學校數理系，江蘇 南通 226000； 2.南通大學理學院，江蘇 南通 226007)

Goldberg snark圖的L(3，2，1)-標號

董曉媛1，馬登舉2

(1.南通師范高等專科學校數理系，江蘇 南通 226000； 2.南通大學理學院，江蘇 南通 226007)

討論了Goldberg snark圖的L(3，2，1)-標號問題，給出了Goldberg snark圖Bk的L(3，2，1)-標號數的界，即11≤λ3，2，1(Bk)≤16.

L(3，2，1)-標號；Goldberg snark圖；標號問題

1 預備知識

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

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

若一個3正則圖是二邊連通且不可3-邊著色的，同時圍長至少為5，也無非平凡3-邊割集，則稱之為snark圖.Petersen圖是最小的snark圖，自1975年以來，更多的snark圖被研究人員發現.本文對Goldberg snark圖的L(3，2，1)-標號進行研究.

圖1 Goldberg snark圖B3的一個畫法

圖2 的一個畫法

2 主要結論及證明

為了研究Goldberg snark圖的L(3，2，1)-標號數，首先研究Goldberg圖Bk的L(3，2，1)-標號數.

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

圖3 的一個L(3，2，1)-標號(豎線前即為)

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

圖4 的一個L(3，2，1)-標號(豎線前面首位相連就是)

同理可以驗證這是一個L(3，2，1)-標號，從而λ3，2，1(Bk)≤16.

引理3 當k≡2(mod 4)時，λ3，2，1(Bk)≤16.

圖5 的一個L(3，2，1)-標號(豎線前面首位相連就是)

同理可以驗證這是一個L(3，2，1)-標號，從而λ3，2，1(B4m+2)≤16.

引理4 當k≡3(mod 4)時，λ3，2，1(Bk)≤16.

圖6 的一個L(3，2，1)-標號(豎線前面首位相連就是)

圖7 圖H

同理可以驗證這是一個L(3，2，1)-標號，故λ3，2，1(B4m+3)≤16.

由以上4個引理可知：

接下來給出λ3，2，1(Bk)的一個下界.

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

假設λ3，2，1(H)≤10.設f是H的一個k-L(3，2，1)-標號，則k≤10.

定理2 Goldberg snark圖Bk的L(3，2，1)-標號數λ3，2，1(Bk)滿足

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

證明因為H是Goldberg snark圖的一個子圖，所以λ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] 翟明清，董琳，呂長虹.圖的L(3，2，1)-標號[J].高校應用數學學報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.

(責任編輯：李亞軍)

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

國家自然科學基金資助項目(11171114，11371207)；南通師范高等專科學校重點資助課題(TSGZ201606).

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

O 157.5 [學科代碼] 110·7470

A