復合樹的L（2，1）-標號研究.pdf

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

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