文献综述
研究价值：图着色是图论研究的主题之一。在无线电通信频率分配的促动下，有了经典着色的推广——图的距离2标号这一迷人的推广概念，也称L(h,k)-标号。对L(h,k)-标号,已有大量的图类—弦图、直径2的图、乘积图等等，均被研究过,或确定标号-数或确定标号-数的界。
定义：给定一个图G及两个非负整数h,k，L(h,k)-着色是指相邻点色差不小于h且距离2的两个点的色差不小于k的G的非负整数点着色。最大色与最小色之间的差称为跨度，所有L(h,k)-着色对应的跨度中最小的称为最小跨度，记之为lambda;h,k(G),称之为图G的lambda;h,k-数.这一概念最初由Griggs和Yeh以h=2,k=1的特殊情形首先提出,在此之前,Robort把h=1,k=1情形作为组合分配问题已研究过.
对于图的距离2标号，有一个很有趣的问题，那就是图的关联图的距离2标号问题，也即图的(d,1)-全标号问题。1995年，Whittlesty、Georges和Mauro首先研究了图G的关联图的L(2,1)-标号。2002年，Havet和Yu称图G的关联图的L(2,1)-标号为图G的(2,1)-全标号，同时将之推广得(d,1)-全标号概念。（(1,1)-全标号即全着色)。Havet和Yu在研究了(d,1)-全标号数的一般规律，给出了(d,1)-全标号数的一个上界，同时提出一个关于(d,1)-全标号数上界的猜想----Havet-Yu猜想：lambda;dTle;Delta; 2d-1，并分情形、限图类具体研究猜想的正确性。
图的全标号问题即研究图的关联图的距离2标号问题。图的关联图可看成图的边-路P3替换图。文献[3-4]对(d,1)-全标号的推广问题——图的边-路替换图的L(d,1)-标号问题进行了研究。文献[5-9]对一些具体替换图如Cartesian积图、拟梯子等的L(d,1)-标号问题进行了研究。
经典着色只对相邻的顶点加以限制条件，距离2标号是对距离不超过2的顶点标号加以限制。实际上，频率的干扰可以是多层次的，因此还可以推广到距离3的限制，即距离3标号L(j,k,l)-标号，由于距离3的限制，故相对距离2的限制，距离3标号问题相对难一些。这方面的研究尚少[10-11]，目前对简单的图如路、圈、完全图等有一些研究。
本课题将讨论一特殊构成图拟梯子的L(2,1,1)-标号问题。
总之，图的距离2着色问题是无线电通信波段分配问题的图论模式，有着很大的探讨空间，它的研究成果对波段分配问题起着推进作用。
参考文献:
[1]J.R.GriggsandR.K.Yeh,Labelinggraphswithaconditionatdistance2[J].SIAMJ.Disc.Math,1992,5:586-595
以上是毕业论文文献综述，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
