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

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

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

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

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

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

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