復(fù)合圖G[K-,k-]的L（2，1）-標(biāo)號.pdf

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

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

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