仙人掌图的L(2，1)-标号(英文)  

On the L(2,1)-labelling of Cacti

作　　者：叶林[1] 金泽民[1] 卜月华[1] 

机构地区：[1]浙江师范大学数学系,浙江金华321004

出　　处：《数学研究》2008年第4期371-383,共13页Journal of Mathematical Study

基　　金：supported by NSFC(10701065),ZJNSF(Y607467);NSF of Department of Education of Zhejiang Province of China(20070441)

摘　　要：一个图G的L(2,1)-标号是给图G上的顶点分配非负整数标号,使得G上相邻的两个点的标号至少相差2,距离为2的两个点的标号则不同.G的L(2,1)-标号数λ(G)是所有能使图G正常标号的最小标号.如果一个图的任何两个圈不含有公共边,则称这个图为仙人掌图.显然树是它的一个子图类.对于任何树T,有△(T)+1≤λ(T)≤△(T)+2.本文中我们证明了在一些条件下,这个界也适用于仙人掌图.An L（2, 1）-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that adjacent vertices have numbers at least 2 apart, and vertices at distance 2 have distinct numbers. The L（2, 1）-labelling number λ（G） of G is the minimum range of labels over all such labels. A graph is a cactus if any two cycles have no public edges, which contains trees as one of its subclasses. For any tree T, △（T） ＋ 1 ≤λ（T） ≤△A（T） ＋ 2. In this paper, we prove that the same bounds also hold for cacti under additional conditions.

关 键 词：L(2 1)-标号 圈 距离 最大度 

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