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

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

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

【相似文獻】

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

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

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

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

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

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

，

本文編號：1154048