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