圖的距離2邊標(biāo)號(hào)數(shù)的上界.pdf

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

2、當(dāng)d(u，v)=2時(shí)，|f(u)-f(v)|≥k．圖G的L(j，k)-標(biāo)號(hào)數(shù)定義為：λ<,j,K>(G)=min<,f> max{f(u)：v∈V(G)}，即圖G的所有L(J，k)-標(biāo)號(hào)的最大標(biāo)號(hào)的最小值。 本文考慮圖的距離2邊標(biāo)號(hào)問題．圖G邊集不空，對(duì)任意的邊e<,1>，e<,2> ∈E(G)，若e<,1>，e<,2>是鄰接的，則我們規(guī)定d(e<,1>，e<,2>)=1；若e<,1>，e<,2>不鄰接，但存在一條邊e使得e<,

3、1>，e<,2>與e都是鄰接的，則規(guī)定d(e<,1>，e<,2>)=2．圖G的L(j，k)．邊標(biāo)號(hào)是一個(gè)從邊集E(G)到非負(fù)整數(shù)集的函數(shù)f滿足條件： (1)|f(e<,1>)-f(e<,2>)|≥j，若d(e<,1>，e<,2>)=1；(2)|f(e<,1>)-f(e<,2>)|≥k，若d(e<,1>，e<,2>)=2．圖G的L(j，k)-邊標(biāo)號(hào)數(shù)定義為：λ'<,j,k>(G)=min<,f>maX{f(e)：e∈E(G))，即圖G的所

4、有L(j，k)-邊標(biāo)號(hào)的最大標(biāo)號(hào)的最小值，簡(jiǎn)單記為λ'<,j,k>-數(shù)．當(dāng)j=1，k=1時(shí)，L(1，1)-邊標(biāo)號(hào)即強(qiáng)邊著色；本文主要考慮j=2，k=1的情況．設(shè)L(G)為G的線圖，則易見λ'<,j,k>(G)=λ<,j,k>(L(G))。 本文主要研究幾類特殊圖的邊標(biāo)號(hào)數(shù)的上界．在第二章中考慮滿足條件：△<,L>(G)=3(其中△<,L>(G)是G的線圖的最大度)的圖G的L(2，1)一邊標(biāo)號(hào)數(shù)的上界．當(dāng)g(G)不超過7(其中g(shù)(