论文部分内容阅读
图的标号问题是图的染色问题的推广,它在现实生活中有着广泛的应用.
本文讨论了图的两种标号问题: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没有Hamilton路,并且△(G)≥2,则λ(G)≤△<2>;此外,当△(G)≥2时,如果Griggs和Yeh的猜想对于图G不正确,则λ(G)≤n-2。其中n表示图G的顶点数。(即当△(G)≥2时,如果λ(G)≥n-1,则λ(G)≤△<2>.)