关于几类图的L(3,2,1)-标号问题

THE L (3,2,1)-LABELING PROBLEM ON GRAPHS

图G的L(2 ,1 )_标号是一个从顶点集V(G)到非负整数集的函数f(x) ,使得若d(x ,y) =1 ,则|f(x) -f(y) |≥ 2 ;若d(x ,y) =2 ,则 |f(x) -f(y) |≥ 1 .图G的L(2 ,1 )_标号数λ(G)是使得G有max{f(v) :v∈V(G) } =k的L(2 ,1 )_标号中的最小数k.该文将L(2 ,1 )_标号问题推广到更一般的情形即L(3,2 ,1 )_标号问题 ,并得出了Kneser图、高度不正则图、Halin图的λ3(G)

An L (2,1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(x)-f(y)|≥2 if d(x,y) =1 and |f(x)-f(y)| ≥1 if d(x,y) =2. The ( L (2,1)-labeling) number λ(G) of G is the smallest number k such that G has an L (2,1)-labeling with max{ f(v):v∈V(G)}=k . The L (2,1)-labeling is extended to the L (3,2,1)-labeling and the upper bounds of λ-3(G) of Kneser graphs, extremely irregular graphs and Halin graphs are derived.