【作者】 邵振东； 刘家壮；

【Author】 SHAO Zhen-dong ,LIU Jia-zhuang(Department of Mathematics, Nanjing University, Nanjing 210093, China; The Irisititute of Mathematics, Shandong University, Jinan 250100,China)

【机构】 南京大学数学系； 山东大学数学研究所；

【摘要】 图的L(2,1)-标号问题由频率分配问题归结而来。图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≥1。图G的L(2,1)-标号数A(G)是使得G有max{f(v):v∈V(G)}=k的L(2,1)-标号中的最小数k。本文将L(2,1)-标号问题推广到更一般的情形即L(4,3,2,1)标号问题,并得出了笛卡儿乘积图的λ4(G)的上界。更多还原

【Abstract】 The L(2 ,1 )-labeling problem is formulated from the frequency assignment problem. 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(G)}=k. In this paper, we extend the L(2,1)-labeling to the L(4,3,2,1)-labeling and derive the upper bounds of λ4(G) of product graphs.更多还原