论文部分内容阅读
图的距离二标号来自频道分配问题：某一区域有若干电台，不同的电台要使用无线电波发送信号，为了避免相互干扰，位置十分接近的电台要使用相差足够远的频道，位置较近的电台要使用有一定相差的频道。将频道分配给电台，目标是在保证电台互不干扰的前提下使用最少的频道资源。图的L(2，1)-标号是一个从点集V(G)到非负整数集的函数f，满足条件：(1)当uv∈E(G)时，|f(u)-f(v)|≥2；(2)当d(u，v)=2时，|f(u)-f(v)|≥1。图G的L(2，1)-标号数定义为：λ<,2，1>(G)=min，max{f(v):v∈V(G)}，即图G的所有L(2，1)-标号的最大标号的最小值。
第二章，对复合树T[K<,n>]的L(2，1)-标号数进行研究。对于任意一棵树，Griggs和Yeh已经证明了λ(T)=△+1或者△+2，而复合树T[K<,n>]的标号数也被证明等于(△+1)n或者(△+1)n+1。本文将结合多重L(2，1)-标号，给出在最大度等于3时，该复合树标号数为(△+1)n的充分条件，并且将进一步讨论当n=2时，T[K<,2>]标号数为(△+1)n的充分条件。
第三章，讨论了另一类复合树的标号问题，即T[K<,n>]的L(2，1)-标号。首先给出最大度等于奇数且n=2和n=3时该复合树的标号数的上界，最后对最大度等于偶数且大于等于4的情形，给出T[K<,n>的标号数的上界。