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

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

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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

1 劉鳳霞;完全二部圖的單色樹(shù)劃分和單色樹(shù)覆蓋[D];南開(kāi)大學(xué);2009年

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

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

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

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

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

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

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

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

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

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

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

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

本文編號(hào)：682389