圖運(yùn)算的彩虹連通度.pdf

1、分類號(hào)密級(jí)公開UDC學(xué)號(hào)20130713005青海師范大學(xué)碩士學(xué)位論文圖運(yùn)算的彩虹連通度研究生姓名延陵風(fēng)楠導(dǎo)師姓名(職稱)冶成福，教授申請(qǐng)學(xué)位類別碩士學(xué)位學(xué)科專業(yè)名稱應(yīng)用數(shù)學(xué)研究方向名稱組合數(shù)學(xué)與圖論論文提交日期2016年3月論文答辯日期2016年6月學(xué)位授予單位青海師范大學(xué)學(xué)位授予日期答辯委員會(huì)主席評(píng)閱人，圖運(yùn)算的彩虹連通度中文摘要對(duì)于一個(gè)頂點(diǎn)著色圖G如果圖G的任意兩個(gè)頂點(diǎn)都被一條內(nèi)部頂點(diǎn)顏色不同的路連通則圖G稱為彩虹頂點(diǎn)連通的這條路

2、稱為彩虹頂點(diǎn)路.圖G的彩虹頂點(diǎn)連通數(shù)表示為rvc(G)是使圖G為彩虹頂點(diǎn)連通所使用的最小的顏色數(shù).如果圖G的每一對(duì)頂點(diǎn)uv都存在一個(gè)彩虹頂點(diǎn)u?v測(cè)地線那么圖G就稱為是強(qiáng)彩虹頂點(diǎn)連通的.使圖G是強(qiáng)彩虹頂點(diǎn)連通所使用的最小顏色數(shù)k稱為圖G的強(qiáng)彩虹頂點(diǎn)連通數(shù).因此對(duì)任意的非平凡連通圖G有rvc(G)≤srvc(G).圖G中的一棵樹T稱為一棵彩虹頂點(diǎn)樹如果樹T的每一個(gè)內(nèi)部頂點(diǎn)都有不同的顏色.對(duì)于一個(gè)圖G=(VE)和頂點(diǎn)集V的一個(gè)子集S其中S中

3、至少有兩個(gè)頂點(diǎn)一棵S斯坦納樹或者一棵斯坦納樹連通S(或者更簡(jiǎn)單的一棵S樹)是圖G的一個(gè)子圖T=(V′E′)其中S?V′.對(duì)于S?V(G)并且|S|≥2如果一棵S斯坦納樹T的內(nèi)部頂點(diǎn)都有不同的顏色則稱它為一棵S斯坦納彩虹頂點(diǎn)樹.對(duì)于圖G的一個(gè)頂點(diǎn)著色，能夠使V(G)的每一個(gè)k子集都有一個(gè)彩虹頂點(diǎn)樹連通所使用的最少顏色數(shù)稱為G的k彩虹頂點(diǎn)指標(biāo)表示為rvxk(G).對(duì)于一個(gè)正整數(shù)k如果圖G的任意兩個(gè)頂點(diǎn)都被k條內(nèi)部頂點(diǎn)不交的彩虹頂點(diǎn)路連通則稱

4、G是彩虹頂點(diǎn)k連通的.彩虹頂點(diǎn)k連通數(shù)是使得圖G是彩虹頂點(diǎn)k連通所使用的最小顏色數(shù)表示為rvck(G).如果一條路的所有邊都著有不同的顏色則稱這條路是一條彩虹路.圖G中的一棵樹T稱為一棵彩虹樹如果樹T的每一條邊都有不同的顏色.對(duì)于S?V(G)并且|S|≥2如果一棵S斯坦納樹T的所有邊都有不同的顏色則稱它為一棵S斯坦納彩虹樹.對(duì)于圖G的一個(gè)邊著色，能夠使S的每一個(gè)k子集都有一個(gè)彩虹樹連通所使用的最少顏色數(shù)稱為G的k彩虹指標(biāo)表示為rxk(G

5、).本文在第一章介紹了文章研究的背景及文章用到的符號(hào).第二章研究了字典積強(qiáng)積卡式積以及直積的彩虹頂點(diǎn)連通數(shù)并且得到這些圖運(yùn)算的彩虹頂點(diǎn)連通數(shù)的一些上界.其次討論了一些網(wǎng)絡(luò)圖積的強(qiáng)彩虹頂點(diǎn)連通性.第三章對(duì)于完全多部圖的3彩虹指標(biāo)補(bǔ)圖的3彩虹指標(biāo)以及強(qiáng)彩虹頂點(diǎn)連通性完全多部圖的k彩虹頂點(diǎn)指標(biāo)補(bǔ)圖的k彩虹頂點(diǎn)指標(biāo)做了相關(guān)研究.第四章得到了給定頂點(diǎn)連通度的彩虹頂點(diǎn)2連通數(shù)的上界.關(guān)關(guān)關(guān)鍵鍵鍵詞詞詞:彩虹連通數(shù)彩虹頂點(diǎn)連通數(shù)k彩虹頂點(diǎn)指標(biāo)彩虹頂點(diǎn)