董曉媛，馬登舉

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

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

董曉媛1，馬登舉2

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

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

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

1 預備知識

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

一個圖G的L(3，2，1)-標號是從圖G的頂點集到非負整數(shù)集的一個映射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)-標號數(shù)是指最小的數(shù)k，使得G有一個k-L(3，2，1)-標號.圖G的L(3，2，1)-標號數(shù)用λ3，2，1(G)表示.翟明清等[3]在2007年得到：對有最大度為Δ的任意圖G，λ3，2，1(G)≤Δ3+2Δ.

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

圖1 Goldberg snark圖B3的一個畫法

圖2 的一個畫法

2 主要結論及證明

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

引理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)-標號數(shù)λ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].高校應用數(shù)學學報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