可滿著色圖和最優(yōu)標號問題.pdf

1、圖的染色問題是圖論中最基本，也是最重要的問題之一．而圖的標號問題作為圖的染色問題的推廣在現(xiàn)實生活中有廣泛的應用． 本文主要討論了圖上的兩種標號問題：L(2，1)．標號和最優(yōu)標號． 給定一個無向圖G，G的一個L(2，1)-標號是指從其頂點集V(G)到非負整數(shù)集的一個映射f，滿足：這里如(u，v)表示u和v之間的距離．若一個L(2，1)-標號中的所有標號都不超過整數(shù)k，則稱之為k-L(2，1)-標號。圖G的L(a，1)-標號

2、數(shù)，記作λ(G)，是使得圖G存在L(2，1)-標號的最小正整數(shù)κ．特別地，若G的某個L(2，1)-標號中的標號是連續(xù)出現(xiàn)的，則稱之為G的一個No-hole L(2，1)-標號．圖G的No-holeL(2，1)-標號數(shù)，記作λ(G)，是使得圖G存在No-hole L(2，1)-標號的最小正整數(shù)k．很顯然λ(G)≥λ(G)．在第二章中我們將把注意力放在上述不等式取等號的情況，并把一個滿足λ(G)=λ(G)的圖G稱為可滿著色圖，否則稱G為非可

3、滿著色圖．本文第二章將給出一些可滿著色圖，主要結果有：(1)：刻畫非可滿著色圖的基本結構．(2)：G是n個頂點m條邊的圖，如果m≤n-2，則G是可滿著色圖除非 (3)：G是n個頂點的圖，如果它的連通分支數(shù)，則G是可滿著色圖．(4)：G是n個頂點m條邊的圖，如果m=n-1，則G是可滿著色圖除非G≌K<,1,n-1>，K<,1,3> ∪ aC<,3> ∪bC<,6>(a+b≥1)，k<,1>∪ aC<,3> ∪ bC<,6>(a+b≥1)．

4、(5)：G是n個頂點的圖，如果它的連通分支數(shù)，則G是可滿著色圖除非。 圖的L(2，1)一標號問題在過去十幾年中已經(jīng)得到了廣泛而深入的研究。J.R.Griggs和R.K.Yeh([19])給出了路、圈、樹等特殊圖類的λ值以及最大度為△的一般圖的λ的上界△<'2>+2A，并且猜想對最大度為△≥2的任意圖有λ(G)≤△<'2>．G．J．Chang和 D.Kuo([2])證明了對最大度為△的任意圖有λ(G)≤△<'2>+△。D.Kr á

5、1和R.Skrekovski([23])又稍做改進，證明了對任何△≥2的圖有λ(G)≤△<'2>+△-1。最新的結果是由Concalves給出的，對任何△≥3的圖有λ(G)≤△<'2>+△-2。目前已有大量的特殊圖被證明滿足J.R.Griggs和R.K.Yeh提出的猜想，本文第三章將給出一些特殊圖的L(2，1)-標號數(shù)的上界，這些特殊圖包括Mycielski圖和無爪圖，同時也研究了樹的L(2，1)-標號數(shù)與其補圖的L(2，1)-標號數(shù)和

6、的上下界． 標號圖(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，．．．，к-1)或者к=1，則稱為不連續(xù)增長路。標號圖(G，L)中所有的不連續(xù)增長路的數(shù)目記為d(G，L)．如果一種標號L使得d(G，L)達到最大就稱為最優(yōu)標號．最優(yōu)標號的問題最先是由M．L．Ga