距離圖的標(biāo)號(hào)著色問題.pdf

1、圖G的標(biāo)號(hào)著色L(2,1)-labeling是一個(gè)從點(diǎn)集V(G)到非負(fù)整數(shù)集的函數(shù)f滿足條件:(1)|f(u)-f(v)|≥2,若uv∈E(G);(2)|f(u)-f(v)|≥1,若d(u,v)=2.圖G的標(biāo)號(hào)著色數(shù)定義為:λ(G)=min<,f>max{f(v):v∈V(G)},即圖G的所有標(biāo)號(hào)著色的最大標(biāo)號(hào)的最小值.圖的標(biāo)號(hào)著色問題來自所謂的頻道分配模型:不同的電臺(tái)要使用無線頻道發(fā)送信號(hào),為了避免相互干擾,位置十分接近的電臺(tái)要使用相

2、差足夠遠(yuǎn)的頻道,位置較近的電臺(tái)要使用有一定相差的頻道.將頻道分配給電臺(tái),目標(biāo)是在保證電臺(tái)互不干擾的前提下使用最少的頻道資源.該文主要研究距離圖的標(biāo)號(hào)著色問題.距離圖G(Z,D)是指這樣一類圖:以整數(shù)集Z為點(diǎn)集, u,v∈Z,u,v相鄰當(dāng)且僅當(dāng)|u-v|∈D(D為自然數(shù)集的一個(gè)子集).D稱為距離集.在第二章中,我們對(duì)一般的距離圖給出了一個(gè)統(tǒng)一的上界,我們證明了對(duì)任意|D|=κ<∞的距離圖,λ(D)≤|D|<'2>+3|D|.由此證明了J.