圖的距離2著色的若干問題.pdf

1、圖的距離2著色來自所謂的頻道分配問題：某一區(qū)域有若干電臺(tái)，不同的電臺(tái)要使用無線電波發(fā)送信號(hào)，為了避免相互干擾，位置十分接近的電臺(tái)要使用相差足夠遠(yuǎn)的頻道，位置較近的電臺(tái)要使用有一定相差的頻道。將頻道分配給電臺(tái)，目標(biāo)是在保證電臺(tái)互不干擾的前提下使用最少的頻道資源。圖G的L(j，k)-標(biāo)號(hào)著色是圖的L(2，1)-標(biāo)號(hào)著色的推廣，它是一個(gè)從點(diǎn)集V(G)到非負(fù)整數(shù)集的函數(shù)，滿足條件：(1)當(dāng)uv∈E(G)時(shí)，|f(u)-f(v)|≥j；(2)當(dāng)d

2、(u，v)=2時(shí)，|f(u)-f(v)|≥k。圖G的L(j，k)一標(biāo)號(hào)數(shù)定義為：λ<,j，k>(G)=min<,f>max{f(v)：v∈V(G)}，即圖G的所有L(j，K)。標(biāo)號(hào)著色的最大標(biāo)號(hào)的最小值。G的一個(gè)m-(j，K)-圓標(biāo)號(hào)著色是這樣的一個(gè)函數(shù)：v(a)→{0，1，2，…，m-*1)且滿足：當(dāng)u和v相鄰時(shí)，|f(u)-f(v)|m≥J；當(dāng)u和v距離為2時(shí)，|f(u)-f(v)|m≥k，這里：|x|m=min{|x|，m-|x|

3、}．G所擁有的m-(j，K)-圓標(biāo)號(hào)著色中的最小的m稱之為G的σ<,j,k>-數(shù)，記之為σ<,j,k>(G)。 在第二章中，在完全圖的cartesiaIl積的λ<,j，k>-數(shù)的已有研究的基礎(chǔ)上，進(jìn)一步研究。證明了當(dāng)n>m≥l且n>2m>4時(shí)，如果j/k≤m，那么λ<,j，k>(K<,n>×K<,m>×K<,l>)=(nm-1)后；如果j/k≥m，那么λ<,j，k>(K<,n>×K<,m>×K<,l>)=(n-1>j+(m-1)

4、k。當(dāng)n>m≥l且n=2m>4時(shí)，如果j/k≤m-1，那么λ<,j，k>(K<,n>×K<,m>×K<,l>)=(nm-1)k；如果j/k≥m-1，那么λ<,j，k>(K,n>×K<,m>×K<,l>)≤(n-1)(j+k)+(m-1)k。當(dāng)m≤n<2m時(shí)，我們也對(duì)λ<,j，k>(K<,n>×K<,m>×K,,l>)做了一些研究。 在第三章中，完全給出了三個(gè)完全圖的cartesian積的λ<,2，1>-數(shù)和σ<,2,1>-數(shù)。