具有完美匹配的三正则图的L（2，1）-标号和毛毛虫的最优标号问题

摘要

图的标号问题是图的染色问题的推广，它在现实生活中有着广泛的应用． 本文讨论了图的两种标号问题：L(2，1)-标号和最优标号．给定一个无向图G，G的一个L(2，1)-标号是指从其顶点集V(G)到非负整数集{0，1，2…．}的一个映射f，满足：这里d<,G>(u，v)表示u和v之间的距离，即u和v之间最短路的长度。若一个L(2，1)-标号中的所有标号都不超过整数足，则称之为k-L(2，1)-标号．图G的L(2，1)-标号数，记作λ(G)，是使得图G存在L(2，1)-标号的最小正整数k。Griggs和Yeh最早研究了L(2，1)-标号问题，他们考虑了λ(G)与X(G)，△(G)，|V(G)|之间的关系．他们得出结论：λ(G)≤△<'2>(G)+2△(G)。并猜想：当图G的最大度△(G)≥2时，都有λ(G)≤△<'2>(G)．本文中，我们定义了图的匹配和的概念，得到λ(G)的一个上界．把这个结果应用于一类特殊的三正则图G，我们得到λ(G)至多是9，这于Griggs和Yeh的猜想相符合．在这里，我们将证明这类特殊的三正则图除了Petersen图的λ(G)=9之外，其余图的λ(G)≤8．并猜想：除了Petersen图之外，所有三正则图的λ(G)至多是7，Petersen图是唯一的λ-数为9的三正则图。 标号图(G，L)由图G和它的标号L∶V(G)→(1，2…，n)组成，其中n=|V(G)|。在标号图(G，L)中，如果一条路(u<,1>，u<,2>,…，u<,k>)满足L(u<,i>)+2≤L(u<,i>+1)(i=1，2…，k-1)或者是一个节点称为不连续增长路。标号图(G，L)中所有的不连续增长路的数目记为d(G，L)。如果一种标号L使的d(G，L)达到最大就称为最优标号。本文给出了Caterpiliar的一种最优标号。 Griggs和Yeh([14])提出了一个非常有趣的猜想：当图G的最大度△≥2时，都有λ(G)≤△<'2>．这个猜想激起了人们对λ-数的研究兴趣。现在已经证明了对于一些特殊的图类这个结论是正确的．而对于一般的图，Griggs和Yeh([14])首先证明了λ(G)≤△<'2>+2△。接下来Chang和Kuo([5])把这个界改进到λ(G)≤△<'2>+△。在([19])中，D.Kr ál和R．Skrekovski又将上界改进为△<'2>+△-1． 在本文中，我们给出下面的定理并加以证明：如果图G的补图G<'c>没有Hamilton路，并且△(G)≥2，则λ(G)≤△<'2>；此外，当△(G)≥2时，如果Griggs和Yeh的猜想对于图G不正确，则λ(G)≤n-2。其中n表示图G的顶点数。(即当△(G)≥2时，如果λ(G)≥n-1，则λ(G)≤△<'2>．)

目录

文摘

英文文摘

学位论文独创性声明及使用授权声明

第一章引言

§1.1背景和基本概念

§1.2主要的相关结果

第二章一类具有完美匹配的三正则图的L（2，1）-标号

§2.1引言

§2.2主要结论

第三章毛毛虫的最优标号

§3.1引言

§3.2主要结论

第四章关于图的L（2，1）-标号数的—点注记

§4.1引言

§4.2主要定理的证明

参考文献

作者申请硕士学位期间所做的工作

致谢