CAJ | 학술논문

给出了图L(d,1,1)-标号的一般性质. 对一般图G, 给出了构造L(d,1,1)-标号的一个算法, 证明了λ_(d,1,1)(G)≤Δ~3-Δ~2+dΔ. 对最大度Δ的树T, 证明了d+Δ-1≤λ_(d,1,1)(T)≤d+2Δ-2, 并且式中的上界与下界都是可达的. 此外, 对于两类特殊的树图: 拟正则树T_Δ及正则毛毛虫Cat_n, 给出了确切的L(d,1,1)-标号数, 其中d≥2.
급출료도L(d,1,1)-표호적일반성질. 대일반도G, 급출료구조L(d,1,1)-표호적일개산법, 증명료λ_(d,1,1)(G)≤Δ~3-Δ~2+dΔ. 대최대도Δ적수T, 증명료d+Δ-1≤λ_(d,1,1)(T)≤d+2Δ-2, 병차식중적상계여하계도시가체적. 차외, 대우량류특수적수도: 의정칙수T_Δ급정칙모모충Cat_n, 급출료학절적L(d,1,1)-표호수, 기중d≥2.
The authors gave some general propositions of L(d, 1,1)-labeling. An upper bound of λ_(d,1,1)(G) was given for any graph with maximum degree △ by an algorithm which is λ_(d,1,1)(G) ≤△~3 -△~2 +d△. For any tree of maximum degree △, we have d + △ - 1 ≤λ_(d,1,1)(T) ≤d + 2△ - 2, moreover, the lower and upper bounds are both attainable. The values of L(d,1 ,1)-labeling number for quasi regular tree T_△ and any regular caterpillar Cat_n were also given, for d≥2.