可滿著色圖和最優(yōu)標(biāo)號(hào)問題.pdf

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

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

3、滿著色圖．本文第二章將給出一些可滿著色圖，主要結(jié)果有：(1)：刻畫非可滿著色圖的基本結(jié)構(gòu)．(2)：G是n個(gè)頂點(diǎn)m條邊的圖，如果m≤n-2，則G是可滿著色圖除非 (3)：G是n個(gè)頂點(diǎn)的圖，如果它的連通分支數(shù)，則G是可滿著色圖．(4)：G是n個(gè)頂點(diǎ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個(gè)頂點(diǎn)的圖，如果它的連通分支數(shù)，則G是可滿著色圖除非。 圖的L(2，1)一標(biāo)號(hào)問題在過去十幾年中已經(jīng)得到了廣泛而深入的研究。J.R.Griggs和R.K.Yeh([19])給出了路、圈、樹等特殊圖類的λ值以及最大度為△的一般圖的λ的上界△<'2>+2A，并且猜想對(duì)最大度為△≥2的任意圖有λ(G)≤△<'2>．G．J．Chang和 D.Kuo([2])證明了對(duì)最大度為△的任意圖有λ(G)≤△<'2>+△。D.Kr á

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

6、的上下界． 標(biāo)號(hào)圖(G，L)由圖G和它的標(biāo)號(hào)L∶V(G)→{1，2，．．，n}組成，其中，n=｜V(G)｜．在標(biāo)號(hào)圖(G，L中，如果一條路u<,1> u<,2>．．．u<,k>滿足L(u<,i>)+2≤L(u<,i+1>)(i=1，2，．．．，к-1)或者к=1，則稱為不連續(xù)增長路。標(biāo)號(hào)圖(G，L)中所有的不連續(xù)增長路的數(shù)目記為d(G，L)．如果一種標(biāo)號(hào)L使得d(G，L)達(dá)到最大就稱為最優(yōu)標(biāo)號(hào)．最優(yōu)標(biāo)號(hào)的問題最先是由M．L．Ga