圖的距離2邊標號數(shù)的上界.pdf

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

2、當d(u，v)=2時，|f(u)-f(v)|≥k．圖G的L(j，k)-標號數(shù)定義為：λ<,j,K>(G)=min<,f> max{f(u)：v∈V(G)}，即圖G的所有L(J，k)-標號的最大標號的最小值。 本文考慮圖的距離2邊標號問題．圖G邊集不空，對任意的邊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)．邊標號是一個從邊集E(G)到非負整數(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)-邊標號數(shù)定義為：λ'<,j,k>(G)=min<,f>maX{f(e)：e∈E(G))，即圖G的所

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