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

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

2、G)，是使得圖G存在L(2，1)-標(biāo)號的最小正整數(shù)k。Griggs和Yeh最早研究了L(2，1)-標(biāo)號問題，他們考慮了λ(G)與X(G)，△(G)，|V(G)|之間的關(guān)系．他們得出結(jié)論：λ(G)≤△<'2>(G)+2△(G)。并猜想：當(dāng)圖G的最大度△(G)≥2時(shí)，都有λ(G)≤△<'2>(G)．本文中，我們定義了圖的匹配和的概念，得到λ(G)的一個(gè)上界．把這個(gè)結(jié)果應(yīng)用于一類特殊的三正則圖G，我們得到λ(G)至多是9，這于Griggs和Y

3、eh的猜想相符合．在這里，我們將證明這類特殊的三正則圖除了Petersen圖的λ(G)=9之外，其余圖的λ(G)≤8．并猜想：除了Petersen圖之外，所有三正則圖的λ(G)至多是7，Petersen圖是唯一的λ-數(shù)為9的三正則圖。 標(biāo)號圖(G，L)由圖G和它的標(biāo)號L∶V(G)→(1，2…，n)組成，其中n=|V(G)|。在標(biāo)號圖(G，L)中，如果一條路(u<,1>，u<,2>,…，u<,k>)滿足L(u<,i>)+2≤L(u

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

5、對于一般的圖，Griggs和Yeh([14])首先證明了λ(G)≤△<'2>+2△。接下來Chang和Kuo([5])把這個(gè)界改進(jìn)到λ(G)≤△<'2>+△。在([19])中，D.Kr ál和R．Skrekovski又將上界改進(jìn)為△<'2>+△-1． 在本文中，我們給出下面的定理并加以證明：如果圖G的補(bǔ)圖G<'c>沒有Hamilton路，并且△(G)≥2，則λ(G)≤△<'2>；此外，當(dāng)△(G)≥2時(shí)，如果Griggs和Yeh的