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

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

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