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

The L(3,2,1)-Labeling Problem on Three Classes of Graphs

作　　者：邵振东[1] 刘家壮[2] 

机构地区：[1]南京大学数学系,江苏南京210093 [2]山东大学数学研究所,山东济南250100

出　　处：《运筹与管理》2004年第5期43-46,共4页Operations Research and Management Science

基　　金：博士后科研启动基金资助项目(0203006211)

摘　　要：图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.

关 键 词：运筹学 频率分配 T-染色 L(2 1)-标号 

分 类 号：O157.5[理学—数学]