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

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

3、滿(mǎn)著色圖．本文第二章將給出一些可滿(mǎn)著色圖，主要結(jié)果有：(1)：刻畫(huà)非可滿(mǎn)著色圖的基本結(jié)構(gòu)．(2)：G是n個(gè)頂點(diǎn)m條邊的圖，如果m≤n-2，則G是可滿(mǎn)著色圖除非 (3)：G是n個(gè)頂點(diǎn)的圖，如果它的連通分支數(shù)，則G是可滿(mǎn)著色圖．(4)：G是n個(gè)頂點(diǎn)m條邊的圖，如果m=n-1，則G是可滿(mǎn)著色圖除非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是可滿(mǎn)著色圖除非。 圖的L(2，1)一標(biāo)號(hào)問(wèn)題在過(guò)去十幾年中已經(jīng)得到了廣泛而深入的研究。J.R.Griggs和R.K.Yeh([19])給出了路、圈、樹(shù)等特殊圖類(lèi)的λ值以及最大度為△的一般圖的λ的上界△<'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。目前已有大量的特殊圖被證明滿(mǎn)足J.R.Griggs和R.K.Yeh提出的猜想，本文第三章將給出一些特殊圖的L(2，1)-標(biāo)號(hào)數(shù)的上界，這些特殊圖包括Mycielski圖和無(wú)爪圖，同時(shí)也研究了樹(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>滿(mǎn)足L(u<,i>)+2≤L(u<,i+1>)(i=1，2，．．．，к-1)或者к=1，則稱(chēng)為不連續(xù)增長(zhǎng)路。標(biāo)號(hào)圖(G，L)中所有的不連續(xù)增長(zhǎng)路的數(shù)目記為d(G，L)．如果一種標(biāo)號(hào)L使得d(G，L)達(dá)到最大就稱(chēng)為最優(yōu)標(biāo)號(hào)．最優(yōu)標(biāo)號(hào)的問(wèn)題最先是由M．L．Ga