圖運算的彩虹連通度.pdf

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

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

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

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

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