摘要
给出了图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Δ及正则毛毛虫Catn,给出了确切的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 Catn were also given,for d≥2.
出处
《吉林大学学报（理学版）》
CAS
CSCD
北大核心
2009年第6期1135-1139,共5页
Journal of Jilin University:Science Edition
基金
国家自然科学基金(批准号:10871166)
关键词
图标号
L(d
1
1)-标号
频率分配
树
graph labeling
L（d
1
1）-labeling
frequency assignment
tree
