具有完美匹配的三正則圖的L（2，1）-標號和毛毛蟲的最優(yōu)標號問題.pdf

1、圖的標號問題是圖的染色問題的推廣，它在現(xiàn)實生活中有著廣泛的應用． 本文討論了圖的兩種標號問題：L(2，1)-標號和最優(yōu)標號．給定一個無向圖G，G的一個L(2，1)-標號是指從其頂點集V(G)到非負整數(shù)集{0，1，2…．}的一個映射f，滿足：這里d<,G>(u，v)表示u和v之間的距離，即u和v之間最短路的長度。若一個L(2，1)-標號中的所有標號都不超過整數(shù)足，則稱之為k-L(2，1)-標號．圖G的L(2，1)-標號數(shù)，記作λ(

2、G)，是使得圖G存在L(2，1)-標號的最小正整數(shù)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和Y

3、eh的猜想相符合．在這里，我們將證明這類特殊的三正則圖除了Petersen圖的λ(G)=9之外，其余圖的λ(G)≤8．并猜想：除了Petersen圖之外，所有三正則圖的λ(G)至多是7，Petersen圖是唯一的λ-數(shù)為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

4、<,i>+1)(i=1，2…，k-1)或者是一個節(jié)點稱為不連續(xù)增長路。標號圖(G，L)中所有的不連續(xù)增長路的數(shù)目記為d(G，L)。如果一種標號L使的d(G，L)達到最大就稱為最優(yōu)標號。本文給出了Caterpiliar的一種最優(yōu)標號。 Griggs和Yeh([14])提出了一個非常有趣的猜想：當圖G的最大度△≥2時，都有λ(G)≤△<'2>．這個猜想激起了人們對λ-數(shù)的研究興趣。現(xiàn)在已經(jīng)證明了對于一些特殊的圖類這個結論是正確的．而

5、對于一般的圖，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的