圖的距離邊標(biāo)號及其相關(guān)問題.pdf

1、設(shè)j和k為兩個非負(fù)整數(shù)，圖的L(j，k)-標(biāo)號是一類圖的距離著色問題，它是從頻道分配問題中抽象出來的著色問題，具有重要的理論價值與應(yīng)用背景。設(shè)m為一個正整數(shù)，圖G的一個m-L(j，k)-標(biāo)號，是指用非負(fù)整數(shù)集{0，1,…，m}中的數(shù)去對圖的頂點進(jìn)行標(biāo)號，使得任意相鄰的兩個頂點到得的標(biāo)號之差至少為j，任意距離為二的兩個頂點得到的標(biāo)號之差至少為k。實際上，圖的L(j，k)-標(biāo)號就是原圖的平方圖的距離著色，它進(jìn)一步拓展了著色理論的實際應(yīng)用范圍

2、。近二十年來，L(j，k)-標(biāo)號得到了廣泛的研究，且研究成果不斷涌現(xiàn)。
　　類似圖的L(j，k)-標(biāo)號，可以得到圖的L(j，k)-邊標(biāo)號。圖G的一個m-L(j，k)-邊標(biāo)號，是指用非負(fù)整數(shù)集{0，1,…，m}中的數(shù)去對圖的邊進(jìn)行標(biāo)號，使得任意相鄰的兩條邊到得的標(biāo)號之差至少為j，任意距離為二的兩條邊得到的標(biāo)號之差至少為k。一個圖的所有m-L(j，k)-標(biāo)號中最小的m稱為該圖的L(j，k)-邊標(biāo)號數(shù)。本文重點研究了一些圖類當(dāng)j=1，k

3、=2時的L(j，k)-邊標(biāo)號數(shù)，即L(1，2)-邊標(biāo)號數(shù)。
　　圖的強(qiáng)邊著色，是一種特殊的距離著色，它要求相鄰的邊得到的顏色不同，距離為二的邊得到的顏色也不相同。實際上，圖的強(qiáng)邊著色也就是圖的L(1，1)-邊標(biāo)號。在頻道分配過程中，如果頻道資源有限，問題就隨之而來，即如果在給定的頻道數(shù)目下，不能得到一個頻道分配使之滿足距離的約束。這時，就要考慮在頻道分配時對距離的約束進(jìn)行放松。設(shè)s和t為兩個非負(fù)整數(shù)，本文提出了(s，t)-放松和μ

4、-放松強(qiáng)邊著色的定義。圖G的一個(s，t)-放松m-強(qiáng)邊著色，是指用m個顏色給邊集著色，使得對圖G的任意一條邊，最多有s條e的鄰邊和t條與e距離為二的邊和e的顏色相同。圖G的(s，t)-放松強(qiáng)邊色數(shù)是指使得G存在(s，t)-放松m-強(qiáng)邊著色的最小整數(shù)m。給定正整數(shù)μ，如果對任意一條邊e，在其鄰邊和距離為二的邊中，最多有μ條邊的顏色和e相同，則稱之為圖G的一個μ-放松m-強(qiáng)邊著色。圖G的μ-放松強(qiáng)邊色數(shù)是指使得G存在μ-放松m-強(qiáng)邊著色的

5、最小整數(shù)m。本文重點研究了樹的(1，0)-放松強(qiáng)邊著色、無窮正則樹的(s，0)-放松和(0，t)-放松強(qiáng)邊著色以及1-放松和2-放松強(qiáng)邊著色。
　　本文得到的主要結(jié)論概括如下:
　　(1)關(guān)于L(1，2)-邊標(biāo)號的研究，主要結(jié)論為:確定了路、圈、完全圖、完全多部圖和輪圖的L(1，2)-邊標(biāo)號數(shù);當(dāng)△=3和4時，確定了無窮△-正則樹的L(1，2)-邊標(biāo)號數(shù)，當(dāng)△≥5時，給出了無窮正則樹的L(1，2)-邊標(biāo)號數(shù)的界;項鏈Neh是

6、一類特殊的Halin圖，當(dāng)1≤h≤4時，確定了Neh的L(1，2)-邊標(biāo)號數(shù)，當(dāng)h≥5時，給出了Neh的L(1，2)-邊標(biāo)號數(shù)的界，并證明了上下界都是可達(dá)的;分別給出了六邊形、四邊形和三角形網(wǎng)格圖的L(1，2)-邊標(biāo)號數(shù)的界。
　　(2)關(guān)于放松強(qiáng)邊著色的研究，主要結(jié)論為:對一般的樹，給出了其(1，0)-放松強(qiáng)邊著色數(shù)的界，并且證明了上界和下界都是可達(dá)的;對無窮正則樹，對任意的正整數(shù)s和t，確定了(s，0)-放松和(0，t)-放松