论文部分内容阅读
图G的L(2，1)标号是一个从顶点集V(G)到非负整数集的函数f(x)，使得若d(x，y)=1，则|f(x)-f(y)|≥2；若d(x，y)=2，则|f(x)-f(y)|≥1．图G的L(2，1)-标号数A(G)是使得G有max{f(v)：v∈V(G))=k的L(2，1)标号中的最小数k．Griggs和Yeh猜想对最大度为△的一般图G，有λ(G)≤Δ^2．本文给出了Kneser图，Mycieklski图，Descartes图，Halin图的λ值的上界，并证明了上述猜想对以上几类图成立。