L(j, k)-labelling and maximum ordering-degrees for trees
L(j, k)-labelling and maximum ordering-degrees for trees
复制标题
L(j, k)-树的标记和最大有序度
DOI：
10.1016/j.dam.2009.11.018
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
E. Friedman
中科院分区：
文献类型：
--
作者：
V. Pavlidis;E. Friedman
设G是一个图。对于G中的两个顶点u和v，记d（u，v）为u和v之间的距离.设j，k为正整数，j ≠ k. G的L（j，k）-标号是函数f：V（G）→{0，1，2，.}使得对于任意两个顶点u和v，|f（u）−f（v）|如果d（u，v）=1，至少为j;如果d（u，v）=2，至少为k。f的跨度是f（V）中最大和最小数之差。G的λj，k-数记为λj，k（G），是G的所有L（j，k）-标号上的最小跨距。我们为树T引入了一个新的参数，即最大有序度，记为M（T）。结合这个新的参数和Chang和Lu（2003）[3]引入的特殊无限树族，我们给出了λj，k（T）关于j，k，M（T）和Δ（T）（T的最大度）的上下界.对于一个特殊情况，当j <$Δ（T）k时，上界和下界相距k。此外，我们完全确定了树T的λj，k（T），其中j <$M（T）k。
Let G be a graph. For two vertices u and v in G, we denote d(u,v) the distance between u and v. Let j,k be positive integers with j⩾k. An L(j,k)-labelling for G is a function f:V(G)→{0,1,2,…} such that for any two vertices u and v, |f(u)−f(v)| is at least j if d(u,v)=1; and is at least k if d(u,v)=2. The span of f is the difference between the largest and the smallest numbers in f(V). The λj,k-number for G, denoted by λj,k(G), is the minimum span over all L(j,k)-labellings of G. We introduce a new parameter for a tree T, namely, the maximum ordering-degree, denoted by M(T). Combining this new parameter and the special family of infinite trees introduced by Chang and Lu (2003) [3], we present upper and lower bounds for λj,k(T) in terms of j, k, M(T), and Δ(T) (the maximum degree of T). For a special case when j⩾Δ(T)k, the upper and the lower bounds are k apart. Moreover, we completely determine λj,k(T) for trees T with j⩾M(T)k.