图的L(d,1,1)-标号 (2009年)

给出了图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。