论文部分内容阅读
图的L(2,1)-标号是从频道分配问题中概括出来的一类图的着色问题,近些年来L(2,1)-标号问题的研究取得了很多成果,L(2,1)-标号概念也被大大推广了。我们考虑如下复杂一些的频道分配模型,进而引出我们的问题。设n和d是正整数,如果某个区域有多个电台,每个电台要发射n个不同的电波信号,为避免干扰,任意两个位置非常接近的信号至少要相距d个频率,而位置比较接近的信号只要频率不同就可以了。用标号的思想来考虑这个问题,就可以把它看成是图的n重L(d,1)-标号。定义任意两个整数集合I和J之间的距离为d(I,J)=min[|i-j|:i∈,I,j∈J}。对于一个给定的图G,它的n重L(d,1)-标号是一个非负整数集函数f:V(G)→非负整数集的所有n子集合的集合,f满足两个条件:
(1)d(f(u),f(v))≥d,若uv∈E(G);
(2)d(f(u),f(v))≥1,若u与v的距离为2。
图G的n重L(d,1)-标号数定义为λnd,1(G)=minfmaxf(v1)∪f(v2)∪…∪f(vn),其中f取遍图G的所有n重L(d,1)-标号。用同样的正多边形去覆盖平面,仅仅正三角形,正六边形,正方形三种网格图是可行的,在第二部分,我们研究三种网格图:正三角形网格,正六边形网格及多维方形网格的n重L(d,1)-标号和n重L(d,1)-圆标号。通过分析论证和对网格图的顶点循环地分配标号集,我们得到了n重L(d,1)-标号数和n重L(d,1)-圆标号数的取值上下界,特别当d=2时,我们完全确定出三种网格的n重L(d,1)-标号数和n重L(d,1)-圆标号数。
在本文第三部分,我们进一步研究了图G的n重d-分离L(d,1)-标号。用Kn表示n个点的完全图,图G的n重d-分离L(d,1)-标号就是复合图G[Kn]的L(d,1)-标号,而图G的n重L(d,1)-标号等价于G[Kcn]的L(d,1)-标号。当d=2时,我们得到了正三角形网格的n重2-分离L(2,1)-标号数取值范围,并且完全确定了正六边形网格与多维方形网格的的n重2-分离L(2,1)-标号数。