论文摘要
图的染色问题是图论中最基本，也是最重要的问题之一。而图的标号问题作为图的染色问题的推广在现实生活中有广泛的应用。本文主要讨论了图上的两种标号问题：L（2，1）-标号和最优标号。给定一个无向图G，G的一个L（2，1）-标号是指从其顶点集V（G）到非负整数集的一个映射f，满足：这里dG（u，v）表示u和v之间的距离。若一个L（2，1）-标号中的所有标号都不超过整数k，则称之为k-L（2，1）-标号。图G的L（2，1）-标号数，记作λ（G），是使得图G存在L（2，1）-标号的最小正整数k。特别地，若G的某个L（2，1）-标号中的标号是连续出现的，则称之为G的一个No-hole L（2，1）-标号。图G的No-hole L（2，1）-标号数，记作（?）（G），是使得图G存在No-hole L（2，1）-标号的最小正整数k。很显然（?）（G）≥λ（G）。在第二章中我们将把注意力放在上述不等式取等号的情况，并把一个满足（?）（G）=λ（G）的图G称为可满着色图，否则称G为非可满着色图。本文第二章将给出一些可满着色图，主要结果有：（1）：刻画非可满着色图的基本结构。（2）：G是n个顶点m条边的图，如果m≤n-2，则G是可满着色图除非G（?）K2（其中K=n/2≥2）。（3）：G是n个顶点的图，如果它的连通分支数C（G）≥[（n+1）/2]，则G是可满着色图。（4）：G是n个顶点m条边的图，如果m=n-1，则G是可满着色图除非G（?）K1，n-1，L1，3∪aC3∪bC6（a+b≥1），K1∪aC3∪bC6（a+b≥1）。（5）：G是n个顶点的图，如果它的连通分支数C（G）≥[n/2]，则G是可满着色图除非G（?）Kk+1∪（k-1）K1（其中k=n/2）。图的L（2，1）-标号问题在过去十几年中已经得到了广泛而深入的研究。J．R．Griggs和R．K．Yeh（[19]）给出了路、圈、树等特殊图类的λ值以及最大度为△的一般图的λ的上界△2+2△，并且猜想对最大度为△≥2的任意图有λ（G）≤△2。G．J．Chang和D．Kuo（[2]）证明了对最大度为△的任意图有λ（G）≤△2+△。D．Král和R．Skrekovski（[23]）又稍做改进，证明了对任何△≥2的图有λ（G）≤△2+△-1。最新的结果是由Concalves给出的，对任何△≥3的图有λ（G）≤△2+△-2。目前已有大量的特殊图被证明满足J．R．Griggs和R．K．Yeh提出的猜想，本文第三章将给出一些特殊图的L（2，1）-标号数的上界，这些特殊图包括Mycielski图和无爪图，同时也研究了树的L（2，1）-标号数与其补图的L（2，1）-标号数和的上下界。标号图（G，L）由图G和它的标号L∶V（G）→{1，2，…，n}组成，其中n=|V（G）|。在标号图（G，L）中，如果一条路U1U2…uk满足L（ui）+2≤L(ui+1)（i=1，2，…，k-1）或者k=1，则称为不连续增长路。标号图（G，L）中所有的不连续增长路的数目记为d（G，L）。如果一种标号L使得d（G，L）达到最大就称为最优标号。最优标号的问题最先是由M．L．Gargano、M．Lewinter和J．F．Malerba（[11]）三个人提出的。他们提出了一个公开问题：给Pn一个标号L使得d（Pn，L）达到最大。后来I．E．Zverovich解决了这个问题，并给出了证明。本文第四章将给出一个简化的证明，并把这个公开问题推广到圈和星图上。