本文關(guān)鍵詞：圖的3-彩虹指標的相關(guān)研究

  更多相關(guān)文章： 3-彩虹指標 控制集 二部圖 圖的運算 分裂圖

【摘要】：2009年,Chartrand, Okamoto, Zhang提出了k-彩虹連通.令G是一個非平凡的連通圖,在G上定義一個邊著色c:E(G)→{1,2,...,k},k∈EN圖G的一個樹是彩虹的,如果這個樹上的邊分別著不同的顏色.使得對圖中任意k個頂點構(gòu)成的集合S都存在一個連接它的彩虹樹T(S (?) V(T))的著色稱為是k-彩虹著色,k-彩虹著色中使用的最少的著色數(shù)稱為k-彩虹指標,記為rxk(G)本文對3-彩虹指標,進行了相關(guān)問題研究.全文共分為六個部分.第一部分簡單介紹了研究問題的背景與現(xiàn)狀,論文的結(jié)構(gòu)和主要結(jié)論.第二部分給出了本文所需的概念和符號以及證明中用到的預備知識.第三部分主要研究圖的3-彩虹指標的上界.該部分首先借助于圖的控制集界定n階連通圖G的3-彩虹指標,并利用它證明了完全二部圖KS,t{3≤s≤t)的3-彩虹指標的緊的上界.并且,對其它完全二部圖K2,t,南我們使用棋盤法得到3-彩虹指標的精確值.其次,我們得到對于無(P5,C5)且最小度大于等于3的n階連通圖G的上界.另外,利用2-連通圖的3-彩虹指標的研究成果,證明了一般圖G的3-彩虹指標的上界,且得到了緊的實例.第四部分主要研究圖的運算的3-彩虹指標.該部分得到了圖的卡式積,字典積,強積,聯(lián)圖,圖的頂點分裂和邊的收縮運算的3-彩虹指標與對應原圖的指標的關(guān)系表達式,并且,對于圖的卡式積運算,證明了達到上界時的充分條件.第五部分主要探究了分裂圖的3-彩虹著色.該部分對于分裂圖G,通過一個算法得到了它的幾乎最優(yōu)的3-彩虹著色.此算法是在對分裂圖的3-彩虹著色特征分析的基礎(chǔ)上,構(gòu)造出了分裂圖的3-彩虹著色,并且證明了該著色使用了rx3(G)+2或rx3(G)+3種顏色.第六部分是本文的結(jié)束語,對本文進行了概括性總結(jié)和未來的展望.
【關(guān)鍵詞】：3-彩虹指標 控制集 二部圖 圖的運算 分裂圖
【學位授予單位】：天津大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 中文摘要4-5
• Abstract5-8
• 第一章 前言8-13
• 1.1 研究背景與定義8-10
• 1.2 論文結(jié)構(gòu)及主要結(jié)論10-13
• 第二章 預備知識13-17
• 2.1 圖的基本概念和符號13-15
• 2.2 基本的性質(zhì)和定理15-17
• 第三章 3-彩虹指標的上界17-27
• 3.1 完全二部圖K_(s,t)的3-彩虹指標17-24
• 3.1.1 3≤s≤t的情形17-19
• 3.1.2 2=s≤t的情形19-24
• 3.2 無(P_5,C_5)圖的3-彩虹指標的界24-25
• 3.3 一般圖的3-彩虹指標的緊的上界25-27
• 第四章 圖的運算的3-彩虹指標27-39
• 4.1 卡式積28-32
• 4.2 字典積32-35
• 4.3 其它圖的運算35-39
• 第五章 分裂圖的3-彩虹著色39-43
• 5.1 算法-分裂圖的3-彩虹著色39-40
• 5.2 算法的有效性40-43
• 第六章 結(jié)束語43-44
• 參考文獻44-47
• 攻讀碩士期間所發(fā)表論文47-48
• 致謝48

【相似文獻】

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

1 賀佩玲;;完全二部圖k_(4,n)去掉兩條邊的交叉數(shù)[J];衡陽師范學院學報;2008年06期

2 賀佩玲;羅志軍;黃元秋;;幾個完全二部圖去掉一條邊的交叉數(shù)[J];河南師范大學學報(自然科學版);2011年02期

3 馮榮權(quán),金珠英;完全二部圖乘積上的Graham pebbling猜想[J];中國科學(A輯);2001年03期

4 王建,邱箏;｛P_4,C_4,S_4｝——分解[J];南通職業(yè)大學學報(綜合版);2001年04期

5 霍美霞;張欽峰;張淑芹;;完全二部圖的λ_4-最優(yōu)性[J];科學技術(shù)與工程;2008年07期

6 潘玉美;莫明忠;;完全二部圖全著色的構(gòu)造[J];廣西科學院學報;2010年01期

7 楊東;王井玉;;完全二部圖的鄰接譜(英文)[J];蘭州大學學報(自然科學版);2011年03期

8 陳綱;;蘊含K_(3,s)-ke的可圖序列[J];廣西科學;2006年03期

9 陳祥恩;胡志濤;王治文;;完全二部圖K_(1,n),K_(2,n)和K_(3,n)的點強可區(qū)別全染色[J];數(shù)學的實踐與認識;2012年11期

10 胡志濤;王治文;陳祥恩;;完全二部圖K_(4,n)的點強可區(qū)別全染色[J];西南大學學報(自然科學版);2013年03期

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

1 劉鳳霞;完全二部圖的單色樹劃分和單色樹覆蓋[D];南開大學;2009年

2 范文文;邊傳遞的完全二部圖及完全二部地圖[D];云南大學;2014年

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

1 傅孟達;完全二部圖K_(4,n)所有符號圖的準虧格上界[D];湖南科技大學;2015年

2 江妙浩;在一些圖上的H-Hopf模結(jié)構(gòu)[D];廣西師范學院;2015年

3 臧玉萍;匹配的anti-Ramsey染色[D];浙江師范大學;2016年

4 劉婷婷;圖的3-彩虹指標的相關(guān)研究[D];天津大學;2015年

5 張穎芳;完全二部圖K_（n，n）的循環(huán)圈分解及邊—平衡指數(shù)集[D];河南理工大學;2009年

6 范文文;局部2-弧傳遞的完全二部圖[D];云南大學;2011年

7 孔浩;圖的均勻（t，，k，d）-樹染色[D];山東大學;2011年

8 龍建軍;一些圖的[r,s,t]染色[D];福州大學;2011年

9 胡志濤;圖的點強可區(qū)別全染色的研究[D];西北師范大學;2013年

10 王井玉;若干圖的譜性質(zhì)研究[D];蘭州大學;2010年

本文編號：682389