圖的L（d,1）-標(biāo)號(hào)著色.pdf

1、圖的標(biāo)號(hào)著色來自所謂的頻道分配問題：某一區(qū)域有若干電臺(tái)，不同的電臺(tái)要使用無線電波發(fā)送信號(hào)，為了避免相互干擾，位置十分接近的電臺(tái)要使用相差足夠遠(yuǎn)的頻道，位置較近的電臺(tái)要使用有一定相差的頻道。將頻道分配給電臺(tái)，目標(biāo)是在保證電臺(tái)互不干擾的前提下使用最少的頻道資源。圖G的L(d，1)-標(biāo)號(hào)著色(d∈Z+)是圖的L(2，1)-標(biāo)號(hào)著色的推廣，它是一個(gè)從點(diǎn)集V(G)到非負(fù)整數(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)-標(biāo)號(hào)著色數(shù)定義為：λd(G)=minfmax{f(v)：v∈V(G)}，即圖G的所有標(biāo)號(hào)著色的最大標(biāo)號(hào)的最小值。 本文考慮一些圖類的L(d，1)-標(biāo)號(hào)著色問題，研究了Regulartiling、聯(lián)圖以及幾類積圖(Cartesianproduct)等一些圖類的L(d，1)-標(biāo)號(hào)著色數(shù)。除Regulartiling及聯(lián)圖之外，文章的主要部分是討論積圖的標(biāo)號(hào)著色，

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