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

论文摘要

图的标号问题是图的染色问题的推广，它在现实生活中有着广泛的应用。本文讨论了图的两种标号问题：L（2，1）-标号和最优标号。给定一个无向图G，G的一个L（2，1）一标号是指从其顶点集V（G）到非负整数集{0，1，2，…}的一个映射f，满足：这里dG（u，v）表示u和v之间的距离，即u和v之间最短路的长度。若一个L（2，1）-标号中的所有标号都不超过整数k，则称之为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）中，如果一条路（u1，u2，…，uk）满足L（ui）+2≤L(ui+1)（i=1，2，…，k-1）或者是一个节点称为不连续增长路。标号图（G，L）中所有的不连续增长路的数目记为d（G，L）。如果一种标号L使的d（G，L）达到最大就称为最优标号。本文给出了Caterpillar的一种最优标号。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的补图Gc没有Hamilton路，并且△（G）≥2，则λ（G）≤△2；此外，当△（G）≥2时，如果Griggs和Yeh的猜想对于图G不正确，则λ（G）≤n-2。其中n表示图G的顶点数。（即当△（G）≥2时，如果λ（G）≥n-1，则λ（G）≤△2。）

论文目录

• 论文摘要
• ABSTRACT
• 第一章 引言
• §1.1 背景和基本概念
• §1.2 主要的相关结果
• 第二章 一类具有完美匹配的三正则图的L（2,1）-标号
• §2.1 引言
• §2.2 主要结论
• 第三章 毛毛虫的最优标号
• §3.1 引言
• §3.2 主要结论
• 第四章 关于图的L（2,1）-标号数的一点注记
• §4.1 引言
• §4.2 主要定理的证明
• 参考文献
• 作者申请硕士学位期间所做的工作
• 致谢