论文部分内容阅读
图的标号着色来自所谓的频道分配问题:某一区域有若干电台,不同的电台要使用无线电波发送信号,为了避免相互干扰,位置十分接近的电台要使用相差足够远的频道,位置较近的电台要使用有一定相差的频道。将频道分配给电台,目标是在保证电台互不干扰的前提下使用最少的频道资源。图G的L(d,1)-标号着色(d∈Z+)是图的L(2,1)-标号着色的推广,它是一个从点集V(G)到非负整数集的函数f满足条件:(1)|f(u)-f(v)|≥d,若uu∈E(G);(2)|f(u)-f(v)|≥1,若d(u,v)=2。图G的L(d,1)-标号着色数定义为:λd(G)=minfmax{f(v):v∈V(G)},即图G的所有标号着色的最大标号的最小值。
本文考虑一些图类的L(d,1)-标号着色问题,研究了Regulartiling、联图以及几类积图(Cartesianproduct)等一些图类的L(d,1)-标号着色数。除Regulartiling及联图之外,文章的主要部分是讨论积图的标号着色,主要包括路积图、路圈积图、圈积图、完全二部图积图、完全二部图与路的积图、完全图与路的积图以及完全图与圈的积图。
在第二、三章中,通过周期标号的方法寻找Regulartiling及几类积图的L(d,1)-标号着色。本文给出Regulartiling及路积图当d≥3时的L(d,1)-标号着色数。再结合d≤2的情形下的结果,Regulartiling及路积图的L(d,1)-标号着色数便完全确定了。此外,还给出了部分路圈积图、圈积图的L(d,1)-标号着色数,其他则是给出其标号着色数的界。
第四章考虑与完全二部图、完全图有关的积图的L(d,1)-标号着色数。通过模标号的方法,得到这些图的L(d,1)-标号着色,从而确定其L(d,1)-标号着色数或者给出界。在最后一章,利用图的L(d,1)-标号着色数与联图的L(d,1)-标号着色数的关系导出一些图的L(d,1)-标号着色数。