復合圖G[K-,k-]的L（2，1）-標號.pdf

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

2、≥1。圖G的L(2，1)-標號數(shù)定義為：λ<,2,1>(G)：min<,f>max{f(v)：v∈V(G))，即圖G的所有L(2，1)-標號中最大標號的最小值。 考慮下面的實際問題：在同一個地區(qū)，有很多電臺，通常情況下每個電臺有多個頻道。本文考慮了每個電臺都需要k個頻道的情況，為了防止頻道之間的相互干擾，同一個電臺的k個頻道要相互區(qū)分，每兩個都至少要相差2，如果兩個電臺v<,0>和v<,1>距離為1，電臺v<,0>的每個頻道和電

3、臺v<,1>的每個頻道都至少要相差2，如果兩個電臺v<,0>和v<,1>距離為2，電臺v<,0>的每個頻道和電臺v<,1>的每個頻道都至少要相差1，這實際上是圖G的一個k重L(2，1)-標號問題。圖G的一個k重L(2，1)一標號問題等價于復合圖G[K<,k>]的L(2，1)．標號問題，其中K<,k>是k個頂點的完全圖。 文章的第二章首先引用復合圖G[H]的定義，然后給出當日為完全圖K<,k>時，復合圖的一些基本性質(zhì)。文章的第三章