关于n-格图及相关图的L(2,1)标号问题

The L (2,1) Labeling Problem on n Lattice and Relative Graph

图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 .移动通讯频率分配问题可以转化为图的L(2 ,1 )标号问题 .将 2 格图及相关图推广到n 格图及相关图 ,并给出了它们的L(2 ,1 )标号 .

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 moving communication frequency assignment problem can be transformed into an L(2,1) labeling problem on a graph.The 2 lattice and relative graph are extended to the n lattice and relative graph,and the L(2,1) labelings of the n lattice and relative graph are given.