仙人掌图的L（2，1）-标号

一个图G的L（2，1）-标号是给图G上的顶点分配非负整数标号，使得G上相邻的两个点的标号至少相差2，距离为2的两个点的标号则不同．G的L（2，1）-标号数λ（G）是所有能使图G正常标号的最小标号．如果一个图的任何两个圈不含有公共边，则称这个图为仙人掌图．显然树是它的一个子图类．对于任何树T，有△（T） ＋ 1 ≤λ（T） ≤△A（T）＋2．本文中我们证明了在一些条件下，这个界也适用于仙人掌图．

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

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) ≤△(T) + 2. In this paper, we prove that the same bounds also hold for cacti under additional conditions.