圖的L（d,1）-標號著色.pdf

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

2、2)|f(u)-f(v)|≥1，若d(u，v)=2。圖G的L(d，1)-標號著色數(shù)定義為：λd(G)=minfmax{f(v)：v∈V(G)}，即圖G的所有標號著色的最大標號的最小值。 本文考慮一些圖類的L(d，1)-標號著色問題，研究了Regulartiling、聯(lián)圖以及幾類積圖(Cartesianproduct)等一些圖類的L(d，1)-標號著色數(shù)。除Regulartiling及聯(lián)圖之外，文章的主要部分是討論積圖的標號著色，

3、主要包括路積圖、路圈積圖、圈積圖、完全二部圖積圖、完全二部圖與路的積圖、完全圖與路的積圖以及完全圖與圈的積圖。 在第二、三章中，通過周期標號的方法尋找Regulartiling及幾類積圖的L(d，1)-標號著色。本文給出Regulartiling及路積圖當d≥3時的L(d，1)-標號著色數(shù)。再結(jié)合d≤2的情形下的結(jié)果，Regulartiling及路積圖的L(d，1)-標號著色數(shù)便完全確定了。此外，還給出了部分路圈積圖、圈積圖的L