圖的距離二邊標號問題.pdf

1、在圖的經(jīng)典的頂點著色(或邊著色)中，我們只要求任意兩個相鄰頂點(或相鄰邊)所著顏色不相同.如果還要求距離為二的頂點(或距離為二的邊)所著顏色也不相同，我們就得到圖的距離二著色(或強邊著色).圖的距離二著色實際上就是原圖的平方圖的頂點著色.平方圖的頂點著色很早就有研究，而直到上個世紀九十年代初才出現(xiàn)一些圖的強邊著色的研究結(jié)果.經(jīng)典的頂點著色和邊著色已經(jīng)有非常豐富的理論結(jié)果，其應用的領域也很廣泛.最近二十年來，關于圖的距離二著色問題和強邊著

2、色問題的研究結(jié)果也不斷涌現(xiàn).作為經(jīng)典著色問題的推廣，距離二著色問題和強邊著色問題研究進一步拓廣了著色理論的實際應用范圍.比如，Gebremedhin、Manne和Potthen在文[29]中綜述了距離二著色問題和一種強邊著色問題在導數(shù)計算中的應用。 設j和k是兩個非負整數(shù)，通常假定j≥k，圖的L(j，k)-標號是距離二著色的一個直接推廣，它最早是在1992年由Griggs和Yeh[38]為了解決一種特殊的頻道分配問題而提出的.它

3、作為經(jīng)典著色的一個重要推廣，得到了廣泛深入的研究.在圖的L(j，k)-標號中，我們用非負整數(shù)對圖的頂點進行標號使得相鄰頂點的標號之間的差至少為j而距離為二的頂點的標號之間的差至少為k.一個圖的所有L(j，k)-標號中最大標號的最小值稱為該圖的L(j，k)-標號數(shù)，圖的圓-L(j，k)-標號是L(j，k)-標號的一個變形，它用一個周長為整數(shù)的圓上的整點對圖的頂點進行標號，要求相鄰頂點的標號在圓上的距離至少為j而距離為二的頂點的標號在圓上的

4、距離至少為k.使得圖有圓-L(j，k)-標號的最小圓的周長稱為圖的圓-L(j，k)-標號數(shù)。我們可以類似地定義圖的L(j，k)-邊標號數(shù)和圓-L(j，k)-邊標號數(shù)，本論文重點研究圖的強邊著色(即圖的L(1，1)-邊標號)、圖的L(2，1)-邊標號和圖的圓-L(2，1)-邊標號。 論文首先研究圖的強邊著色，證明除了一個僅六個頂點的特殊圖外，對任意圖G，如果對圖G的任一條邊xy都有d(x)+d(y)≤5，那么它的強邊色數(shù)不超過6.

5、因為完全二部圖K2，3滿足上述條件且其強邊色數(shù)為6，所以上界6是最好可能的。這個結(jié)果回答了Faudree等人[22]提出的第四個問題，事實上我們不要求G是二部圖，所以這個結(jié)論比問題要求的更強.該結(jié)果推進了強邊色數(shù)上界的研究，有重要的理論意義.我們還設計了一個算法，它可以在線性時間內(nèi)對滿足上述定理條件的圖給出它的一個6-強邊著色，該算法具有潛在的應用價值。 Georges和Mauro在文[33]中完全確定了無窮△-正則樹的L(2

6、，1)-邊標號數(shù)，接著對任意正整數(shù)△，我們確定了無窮△-正則樹的圓-L(2，1)-邊標號數(shù).設n≥2是一正整數(shù)，Qn，表示n-維立方體.Georges和Mauro在文[33]中研究了當n較小時Qn的L(2，1)-邊標號數(shù)，我們充分利用Qn的結(jié)構(gòu)特征和圓標號的循環(huán)性質(zhì)確定了Q2、Q3、Q4和Q5的圓-L(2，1)-邊標號數(shù)以及Q5的L(2，1)-邊標號數(shù).我們在利用圓-L(2，1)-邊標號數(shù)確定L(2，1)-邊標號數(shù)這方面作了有益的嘗試，

7、有望使用這一手段確定更多的圖的L(2，1)-標號數(shù)。 網(wǎng)格圖的研究是一項很有意義的工作，本論文最后集中研究三種無窮網(wǎng)格圖的L(2，1)-邊標號、圓-L(2，1)-邊標號和強邊著色.分別用г6、г4和г3表示無窮六邊形、四邊形和三角形網(wǎng)格圖，我們證明了г6的強邊色數(shù)為6，L(2，1)-邊標號數(shù)為7，圓-L(2，1)-邊標號數(shù)為8.用Pm□Pn表示兩條路Pm和Pn的笛卡爾乘積圖.我們又得到了一些情況下Pm口Pn的L(2，1)-邊標號