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

The L(3,2,1)-Labeling Problem on Three Classes of 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)标号问题,并得到了平面三角剖分图、立体四面体剖分图的λ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. We generalize the L(2,1)-labeling to the L(3,2,1)-labeling and derive the upper bounds of λ_3(G) of plane triangulation graph, solid tetrahedron subdivision graph.