考慮含有完全圖K4的圖的補圖的L（2，1）-標號的島序列＊

雒金梅，余 航，任樹鑫，郭海防

（西安工業(yè)大學 北方信息工程學院，西安710200）

L（2，1）-標號，由Griggs和Roberts提出的，是產生于各種頻率分配問題的一個頂點標號問題，目的是找到最小的頻率使用范圍，同時確保充分靠近的兩個傳輸機分配到的傳輸頻率的差不小于一個給定的正數［1-2］．L（p，q）-標號是圖G 的頂點集到整數集的一個映射，并且滿足任意兩個相鄰的頂點的標號差至少為p，任意兩個距離為2的頂點標號差至少為q，若p＝2，q＝1那么L（p，q）-標號就是著名的L（2，1）-標號，它是L（p，q）-標號的一種特殊情況．關于L（p，q）-標號，一些專家已經對某些特殊的簡單圖做了研究，特別是對L（2，1）-標號進行了討論．對任意的圖，文獻［3］研究了圖變量λ（G）和圖G的其他圖變量，如圖G的色數χ（G），最大度Δ＝Δ（G）之間的關系，已經得到各種類型的圖的λ數，如樹，圈，路，3-連通圖．文獻［4］研究了弦圖的λ數．另外文獻［5］研究了λ（G）、圖變量c（GC）（圖G的補圖的路覆蓋數）及圖G的頂點數之間的關系．L（2，1）-標號的推廣已經在研究．文獻［6-9］證明了當c（GC）≥2，λ（G）＝n＋c（GC）-2，其中n為圖G的頂點數，給出了路覆蓋的一個更一般的結果的完全證明，證明了圖G的補圖的一個路覆蓋導出了G的一個有c（GC）-1個洞的λ（G）標號．文獻［10］提出了ρ（G）≥1，導出兩個不同島序列的λ（G）標號的連通圖的存在性，證明了2-稀疏數的補圖是容許至少兩個不同島序列的連通圖．文中給出了另一類圖的λ數和洞指數ρ（G）的關系，路覆蓋數和L（2，1）-標號的島序列，研究某類含有完全圖K4的圖的路覆蓋數，以期在兩種最小路覆蓋之下均證明其補圖的兩個不同的λ標號導出的兩個……