復(fù)合樹(shù)的L（2，1）-標(biāo)號(hào)研究.pdf

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

2、G的L(2，1)-標(biāo)號(hào)數(shù)定義為：λ<,2，1>(G)=min，max{f(v):v∈V(G)}，即圖G的所有L(2，1)-標(biāo)號(hào)的最大標(biāo)號(hào)的最小值。 第二章，對(duì)復(fù)合樹(shù)T[K<'c><,n>]的L(2，1)-標(biāo)號(hào)數(shù)進(jìn)行研究。對(duì)于任意一棵樹(shù)，Griggs和Yeh已經(jīng)證明了λ(T)=△+1或者△+2，而復(fù)合樹(shù)T[K<'c><,n>]的標(biāo)號(hào)數(shù)也被證明等于(△+1)n或者(△+1)n+1。本文將結(jié)合多重L(2，1)-標(biāo)號(hào)，給出在最大度等于3