CAJ | 학술논문

一个图G的L(2,1).标号是给图G上的顶点分配非负整数标号,使得G上相邻的两个点的标号至少相差2,距离为2的两个点的标号则不同.G的L(2,1)-标号数λ(G)是所有能使图G正常标号的最小标号.如果一个图的任何两个圈不含有公共边,则称这个图为仙人掌图.显然树是它的一个子图类.对于任何树T,有△(T) + 1 ≤λ(T) ≤△(T)+2.本文中我们证明了在一些条件下,这个界也适用于仙人掌图.
일개도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) ≤△(T) + 2. In this paper, we prove that the same bounds also hold for cacti under additional conditions.