本文關(guān)鍵詞：關(guān)于特殊圖的彩虹連通數(shù)的研究

  更多相關(guān)文章： 特殊圖 彩虹連通數(shù) 彩虹頂點(diǎn)連通數(shù)

【摘要】：著名的格尼斯堡七橋問題是圖論問題的起源,隨后圖論便成為應(yīng)用數(shù)學(xué)研究中的一個(gè)重要分支。特殊圖的染色問題一直是圖論研究領(lǐng)域的熱門問題,它不但具有理論價(jià)值,更具有重要的現(xiàn)實(shí)意義。連通性是圖論中最重要的性質(zhì)之一,基于這些方面,一種加強(qiáng)版的連通性概念——圖的彩虹連通性的問題應(yīng)運(yùn)而生。在2008年,Chartrand、Johnson等人最先把這個(gè)概念引入到文獻(xiàn)中。在過去的幾年里,圖的彩虹連通數(shù)一直作為圖論中的熱門問題受到眾多數(shù)學(xué)專家的廣泛關(guān)注,同時(shí)也被應(yīng)用到網(wǎng)絡(luò)信息安全、密碼學(xué)等領(lǐng)域。如果G是一個(gè)非平凡連通圖,對(duì)G的邊全部染上顏色。若用數(shù)字表示顏色,則c:E(G)→ {1,2,…,kk∈N}即G為的一種著色方式。當(dāng)經(jīng)過圖G中的一條路P上的邊都被染成不同顏色時(shí),則稱路P為圖G的一條彩虹路。如果對(duì)于連通圖G來說,任意兩點(diǎn)間都存在一條彩虹路,則稱圖G是彩虹連通的。稱使得圖G為彩虹路連通的所使用的最少顏色數(shù)k為圖G的彩虹連通數(shù),記為rc(G)。其后,Krivelevich和Yuster提出了彩虹頂點(diǎn)連通的概念。顯然這是對(duì)圖形的頂點(diǎn)進(jìn)行染色。一個(gè)連通圖的任意兩個(gè)頂點(diǎn)之間至少存在一條內(nèi)部頂點(diǎn)染成不同顏色的路相連,則稱該圖是彩虹頂點(diǎn)連通的。類比圖的彩虹連通數(shù)的概念可知,彩虹頂點(diǎn)連通數(shù)就是使得連通圖G彩虹頂點(diǎn)連通的所必須的起碼的顏色數(shù),記為rvc(G)。本文研究了一些特殊圖的彩虹連通性的問題,主要結(jié)果如下：(1)介紹了彩虹連通性問題的基本概念和已有的結(jié)論。(2)利用數(shù)學(xué)歸納法、分類討論思想,計(jì)算出了完全圖刺圖、圈的刺圖、風(fēng)車圖的彩虹連通數(shù)及強(qiáng)彩虹連通數(shù)。(3)運(yùn)用數(shù)學(xué)歸納法和分類討論的的數(shù)學(xué)思想,將原有圖進(jìn)行推廣,對(duì)一些日暈圖的彩虹連通數(shù)問題進(jìn)行了研究。(4)對(duì)3-連通圖的彩虹頂點(diǎn)連通數(shù)進(jìn)行了求解。
【學(xué)位授予單位】：大連海事大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

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

1 陳莉莉;關(guān)于圖的彩虹（頂點(diǎn)）連通數(shù)若干問題的研究[D];南開大學(xué);2014年

2 李恒哲;圖的彩虹連通數(shù)與距離[D];南開大學(xué);2013年

3 董九英;圖的彩虹連通數(shù)的若干上界[D];南開大學(xué);2013年

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

1 劉怡筱;關(guān)于特殊圖的彩虹連通數(shù)的研究[D];大連海事大學(xué);2016年

，

本文編號(hào)：1154048