本文關(guān)鍵詞：關(guān)于圖的幾類標(biāo)號(hào)問題，由筆耕文化傳播整理發(fā)布。

【摘要】：本學(xué)位論文所研究的幾類標(biāo)號(hào)問題都是源自于無線電頻率分配為背景距離2標(biāo)號(hào)問題.圖G的一個(gè)κ-L(2,1)-標(biāo)號(hào)就是從V(G)到{0,1,…,κ}的一個(gè)映射使得相鄰的兩個(gè)頂點(diǎn)取得的值至少相差p,距離為2的兩個(gè)頂點(diǎn)取得的值至少相差q.圖的(d,1)-全標(biāo)號(hào)問題就是L(p,q)-標(biāo)號(hào)問題衍生出來的一種新的標(biāo)號(hào)問題.圖G的一個(gè)κ-((d,1)-全標(biāo)號(hào)就是從V(G) U E(G)到{0,1,…,κ}的一個(gè)函數(shù)使得相鄰的兩個(gè)頂點(diǎn)取值不同,相鄰的兩條邊取值不同,相關(guān)聯(lián)的頂點(diǎn)與邊取得的值至少相差d.與(2,1)-全標(biāo)號(hào)類似,圖G的一個(gè)κ-(2,1)-點(diǎn)面標(biāo)號(hào)就是從V(G)∪ F(G)到{0,1,…,κ}的一個(gè)映射使得相鄰的兩個(gè)點(diǎn)取值不同,相鄰的兩個(gè)面取值不同,相關(guān)聯(lián)的頂點(diǎn)和面取得的值至少相差2.本學(xué)位論文主要圍繞這幾類標(biāo)號(hào)問題開展研究,共分為四章.第一章,我們給出了圖論的一些基本概念與術(shù)語,并介紹了L(p,q)-標(biāo)號(hào)問題以及(d,1)-全標(biāo)號(hào)問題的研究背景和研究進(jìn)展,同時(shí)簡要羅列了本學(xué)位論文的主要研究結(jié)果.第二章,我們主要研究了最大度為3的樹的L(2,1)-標(biāo)號(hào)數(shù)的刻畫問題.首先,我們給出了最大度為3的樹的一個(gè)結(jié)構(gòu)引理.然后,通過我們定義的一個(gè)標(biāo)號(hào)過程,把一些含有特定結(jié)構(gòu)的樹定義為好的.最后,我們證明了最大度為3的樹的L(2,1)-標(biāo)號(hào)數(shù)為△+1當(dāng)且僅當(dāng)樹T是好的.第三章,我們研究了圖的(2,1)-全標(biāo)號(hào)問題,得到了兩個(gè)第一類(即(2,1)-全標(biāo)號(hào)數(shù)是△+1)的樹的充分條件：(I)對(duì)于△4的樹T,如果每一個(gè)大點(diǎn)至多與△-3個(gè)大點(diǎn)相鄰,那么T就是第一類的；(Ⅱ)對(duì)于△≥9的樹T,如果T中不存在兩個(gè)距離為偶數(shù)的壞點(diǎn),那么T就是第一類的.此外,我們還證明了外平面圖的(2,1)-全標(biāo)號(hào)數(shù)至多為△+2.第四章,我們介紹了一個(gè)新的概念——圖的(2,1)-點(diǎn)面標(biāo)號(hào)問題,并針對(duì)幾個(gè)簡單圖類給出了其(2,1)-點(diǎn)面標(biāo)號(hào)數(shù)的緊的上界,如樹、圈、歐拉二部圖、K4、外平面圖等.另外,我們還刻畫了至多含有一個(gè)閉內(nèi)面的外平面圖的(2,1)-點(diǎn)面標(biāo)號(hào)數(shù).
【關(guān)鍵詞】：圖 樹 L(2 1)-標(biāo)號(hào) (2 1)-全標(biāo)號(hào) (2 1)-點(diǎn)面標(biāo)號(hào)
【學(xué)位授予單位】：蘇州大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5
【目錄】：

• 摘要4-6
• Abstract6-10
• 第一章 緒論10-21
• 1.1 基本概念11-13
• 1.2 兩類標(biāo)號(hào)問題的研究背景及其進(jìn)展13-19
• 1.2.1 L(2,1)-標(biāo)號(hào)問題13-17
• 1.2.2 (2,1)-全標(biāo)號(hào)問題17-19
• 1.3 主要結(jié)果19-21
• 第二章 樹的L(2,1)-標(biāo)號(hào)21-59
• 2.1 結(jié)構(gòu)引理21-28
• 2.2 最大度為3的樹的L(2,1)-標(biāo)號(hào)數(shù)的刻畫28-59
• 2.2.1 充分性41-54
• 2.2.2 必要性54-59
• 第三章 圖的(2,1)-全標(biāo)號(hào)59-103
• 3.1 樹的(2,1)-全標(biāo)號(hào)59-81
• 3.1.1 充分條件Ⅰ59-67
• 3.1.2 充分條件Ⅱ67-81
• 3.2 外平面圖的(2,1)-全標(biāo)號(hào)81-103
• 3.2.1 △(G)≤3的情況81-83
• 3.2.2 △=4的情況83-100
• 3.2.3 △≥5的情況100-103
• 第四章 圖的(2,1)-點(diǎn)面標(biāo)號(hào)103-114
• 4.1 一些簡單圖類的(2,1)-點(diǎn)面標(biāo)號(hào)103-106
• 4.2 外平面圖的(2,1)-點(diǎn)面標(biāo)號(hào)106-114
• 參考文獻(xiàn)114-119
• 攻讀博士期間完成的論文119-120
• 致謝120-12

【相似文獻(xiàn)】

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

1 王新紅;外平面圖的L(2,1)-標(biāo)號(hào)[J];數(shù)學(xué)研究與評(píng)論;2003年03期

2 戰(zhàn)新剛;一類外平面圖的有界染色[J];山東大學(xué)學(xué)報(bào)(理學(xué)版);2004年01期

3 陳勇,張少強(qiáng);一個(gè)求外平面圖最小反饋點(diǎn)集的多項(xiàng)式時(shí)間算法[J];濟(jì)南大學(xué)學(xué)報(bào)(自然科學(xué)版);2004年01期

4 宋慧敏,吳建良;幾乎外平面圖的邊染色[J];山東大學(xué)學(xué)報(bào)(工學(xué)版);2004年04期

5 孔立;關(guān)于Euler公式的一個(gè)應(yīng)用[J];山東電大學(xué)報(bào);2004年04期

6 鞏在武,孟憲勇;低度外平面圖的點(diǎn)強(qiáng)全染色[J];山東科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2004年03期

7 張少強(qiáng),王驍力,李國君;一個(gè)求外平面圖最小頂點(diǎn)賦權(quán)反饋點(diǎn)集的線性時(shí)間算法(英文)[J];數(shù)學(xué)研究與評(píng)論;2004年04期

8 孔立,倪亞洲;雙外平面圖的邊染色[J];山東教育學(xué)院學(xué)報(bào);2004年06期

9 孔立;雙外平面圖的邊面染色[J];煙臺(tái)師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2005年02期

10 孔立;一個(gè)特殊的雙外平面圖的全染色[J];洛陽大學(xué)學(xué)報(bào);2005年02期

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

1 馮紀(jì)先;;標(biāo)定的最大外平面圖G_(MO)的數(shù)目[A];第十六屆電工理論學(xué)術(shù)年會(huì)論文集[C];2004年

2 馮紀(jì)先;;最大外平面圖G_(MO)的度[A];第十九屆電工理論學(xué)術(shù)年會(huì)論文集[C];2007年

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

1 陳東;關(guān)于圖的幾類標(biāo)號(hào)問題[D];蘇州大學(xué);2015年

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

1 劉廣德;雙外平面圖的點(diǎn)染色[D];山東大學(xué);2008年

2 孔立;雙外平面圖的染色問題[D];山東大學(xué);2005年

3 劉維;外平面圖的列表著色[D];華中師范大學(xué);2012年

4 單偉;幾類圖的雙約束邊染色問題[D];山東大學(xué);2008年

5 許豐偉;圖的完全可定向性[D];浙江師范大學(xué);2010年

6 方峻峰;平面圖染色問題的研究[D];山東科技大學(xué);2003年

7 邵澤玲;外平面圖的松弛競賽色數(shù)[D];河北工業(yè)大學(xué);2003年

8 張少君;圖的若干特殊正常全染色[D];西北師范大學(xué);2006年

9 柳順義;若干圖類的強(qiáng)邊著色[D];西北師范大學(xué);2008年

10 湯宇翔;圖的L（d，1）-標(biāo)號(hào)[D];浙江師范大學(xué);2009年

  本文關(guān)鍵詞：關(guān)于圖的幾類標(biāo)號(hào)問題，由筆耕文化傳播整理發(fā)布。

，

本文編號(hào)：336002