图的L(3,2,1)-标号  

L(3,2,1)-labeling of graphs

作　　者：翟明清[1] 董琳[2] 吕长虹[2] 

机构地区：[1]滁州学院数学系,安徽滁州239012 [2]华东师范大学数学系,上海200062

出　　处：《高校应用数学学报（A辑）》2007年第2期240-246,共7页Applied Mathematics A Journal of Chinese Universities(Ser.A)

基　　金：国家自然科学基金(1030101060673048);安徽省教育厅自然科学基金(2006KJ085BKJ2007B124)

摘　　要：无向图G的L(3,2,1)-标号是指从顶点集V(G)到非负整数集Z*的一个映射,满足:对i=1,2,3,只要dG(x,y)=i,则f(x)-f(y)|≥4-i.若一个L(3,2,1)-标号中的所有像元素都不超过整数k,则称之为k-L(3,2,1)-标号.图G的L(3,2,1)-标号数,记作3λ(G),是使得图G存在k-L(3,2,1)-标号的最小整数k.文中给出了路、圈、树等特殊图的L(3,2,1)-标号数,并给出了一般图的L(3,2,1)-标号数的一个上界.For a given undirected graph G, an L（3,2,1）-labeling is defined as a function f ：V（G）→{0,1,2…}such that ｜f（u）-f（υ）｜≥3 when dG（u,υ）=1, ｜f（u）-f（υ）｜≥2 when dG（u,υ）=2 and ｜f（u）-f（υ）｜≥1 when dG（u,υ）=1. A k-L（3,2,1）- labeling is an L（3,2, 1）-labeling such that no label is greater than k. The L（3,2,1）- labeling number of G, denoted by λ3（G）, is the smallest number k such that G has a k- L（3,2,1）-labeling. This paper gives the values of L（3,2,1）-labeling number for path, cycle and tree. Moreover, an upper bound of λ3（G） is given for any graph.

关 键 词：L(2 1)-标号 L(3 2 1)-标号 算法 树 

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