董晓媛，马登举

(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 的……