本文關(guān)鍵詞：圖的距離邊標(biāo)號(hào)及其相關(guān)問(wèn)題

  更多相關(guān)文章： L(j k)-標(biāo)號(hào) L(j k)-邊標(biāo)號(hào) 強(qiáng)邊著色 (s t)-放松強(qiáng)邊著色 μ-放松強(qiáng)邊著色 無(wú)窮正則樹(shù) 輪圖 Halin圖 項(xiàng)鏈 六邊形網(wǎng)格圖 四邊形網(wǎng)格圖 三角形網(wǎng)格圖

【摘要】：設(shè)j和k為兩個(gè)非負(fù)整數(shù),圖的L(j,k)-標(biāo)號(hào)是一類圖的距離著色問(wèn)題,它是從頻道分配問(wèn)題中抽象出來(lái)的著色問(wèn)題,具有重要的理論價(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)用范圍。近二十年來(lái),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=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)。在頻道分配過(guò)程中,如果頻道資源有限,問(wèn)題就隨之而來(lái),即如果在給定的頻道數(shù)目下,不能得到一個(gè)頻道分配使之滿足距離的約束。這時(shí),就要考慮在頻道分配時(shí)對(duì)距離的約束進(jìn)行放松。設(shè)s和t為兩個(gè)非負(fù)整數(shù),本文提出了(s,t)-放松和β-放松強(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)邊著色的最小整數(shù)m。本文重點(diǎn)研究了樹(shù)的(1,0)-放松強(qiáng)邊著色、無(wú)窮正則樹(shù)的(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í),確定了無(wú)窮△-正則樹(shù)的L(1,2)-邊標(biāo)號(hào)數(shù),當(dāng)△≥5時(shí),給出了無(wú)窮正則樹(shù)的L(1,2)-邊標(biāo)號(hào)數(shù)的界；項(xiàng)鏈Neh是一類特殊的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ì)一般的樹(shù),給出了其(1,0)-放松強(qiáng)邊著色數(shù)的界,并且證明了上界和下界都是可達(dá)的；對(duì)無(wú)窮正則樹(shù),對(duì)任意的正整數(shù)s和t,確定了(s,0)-放松和(0,t)-放松強(qiáng)邊色數(shù),并確定了1-放松和2-放松強(qiáng)邊色數(shù)。
【學(xué)位授予單位】：東南大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

1 王淑棟,龐善臣;系列平行圖的邊色數(shù)[J];山東科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2002年02期

2 牟海波;串圖的邊色數(shù)[J];蘭州鐵道學(xué)院學(xué)報(bào);2003年03期

3 田雙亮;若干n重積圖的點(diǎn)可區(qū)別邊色數(shù)[J];西北民族大學(xué)學(xué)報(bào)(自然科學(xué)版);2005年02期

4 尹志剛;費(fèi)旭云;李曉彪;何建新;;關(guān)于圖的圓邊色數(shù)幾個(gè)重要定理[J];高師理科學(xué)刊;2011年04期

5 王艷麗;苗連英;;圖的集合邊色數(shù)[J];山東大學(xué)學(xué)報(bào)(理學(xué)版);2012年06期

6 賈振聲;何滿年;張忠輔;;關(guān)于圖的3—邊色數(shù)[J];太原重型機(jī)械學(xué)院學(xué)報(bào);1992年01期

7 卓新建;邊色數(shù)為Δ的一個(gè)充分條件[J];曲阜師范大學(xué)學(xué)報(bào)(自然科學(xué)版);1995年04期

8 劉二根;廣義圖K(5,n)的邊色數(shù)[J];華東交通大學(xué)學(xué)報(bào);1997年02期

9 田雙亮,張忠輔;積圖鄰強(qiáng)邊色數(shù)的注記[J];蘭州交通大學(xué)學(xué)報(bào);2005年03期

10 瞿曉鴻;;一個(gè)特殊圖形的邊色數(shù)[J];昆明理工大學(xué)學(xué)報(bào)(理工版);2006年02期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前4條

1 劉華;趙鵬;馬明;冶建華;張忠輔;;圖S_m*F_n的鄰點(diǎn)可區(qū)別的邊色數(shù)[A];中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（中卷）[C];2004年

2 包世堂;;關(guān)于C_m懔C_n的邊色數(shù)[A];中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（上卷）[C];2004年

3 趙傳成;;關(guān)于C_m·S_n和C_mΔSn的邊色數(shù)[A];中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（中卷）[C];2004年

4 馬剛;;S_m∨F_n的全色數(shù)和點(diǎn)可區(qū)別邊色數(shù)[A];中國(guó)運(yùn)籌學(xué)會(huì)第九屆學(xué)術(shù)交流會(huì)論文集[C];2008年

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前1條

1 賀丹;圖的距離邊標(biāo)號(hào)及其相關(guān)問(wèn)題[D];東南大學(xué);2015年

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

1 楊海珍;一些圖的圓邊色數(shù)[D];首都師范大學(xué);2008年

2 章文超;圖的貪婪博弈邊色數(shù)和游戲邊色數(shù)[D];浙江師范大學(xué);2014年

3 毛新葉;圖的點(diǎn)可區(qū)別邊染色的一些結(jié)果[D];西北師范大學(xué);2009年

4 劉利群;圖的D（2）-點(diǎn)可區(qū)別及點(diǎn)可區(qū)別正常邊染色[D];西北師范大學(xué);2007年

5 田京京;圖的D（β）-點(diǎn)可區(qū)別邊染色及其概率方法[D];西北師范大學(xué);2007年

6 楊玉紅;若干圖類的星邊染色[D];西北師范大學(xué);2009年

7 鄧凱;圖的星邊染色[D];西北師范大學(xué);2007年

8 薄朝升;星著色和強(qiáng)邊著色的研究[D];重慶大學(xué);2011年

9 王曉琦;若干合成圖的星邊染色和星全染色[D];西北民族大學(xué);2013年

10 楊清軍;一些特殊圖的強(qiáng)邊著色和平方自由著色[D];重慶大學(xué);2010年

，

本文編號(hào)：1207191