圖的彩虹連通數(shù)的若干上界

《圖的彩虹連通數(shù)的若干上界》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

1、中圖分類號：UDC：學校代碼：10055密級：公開高忿犬淫博士學位論文圖的彩虹連通數(shù)的若干上界UpperBoundsontheRainbowConnectionNumberofGraphs南開大學研究生院二O一三四月南開大學學位論文使用授權書根據(jù)《南開大學關于研究生學位論文收藏和利用管理辦法》，我校的博士、碩士學位獲得者均須向南開大學提交本人的學位論文紙質本及相應電子版。本人完全了解南開大學有關研究生學位論文收藏和利用的管理規(guī)定。南開大學擁有在《著作權法》規(guī)定范圍內的學位論文使用權，即：(1)學位獲得者必須按規(guī)定提交學位論文(包括紙質印刷本及電子版)，學?？梢圆捎糜?/p>

2、印、縮印或其他復制手段保存研究生學位論文，并編入《南開大學博碩士學位論文全文數(shù)據(jù)庫》：(2)為教學和科研目的，學校可以將公開的學位論文作為資料在圖書館等場所提供校內師生閱讀，在校園網上提供論文目錄檢索、文摘以及論文全文瀏覽、下載等免費信息服務；(3)根據(jù)教育部有關規(guī)定，南開大學向教育部指定單位提交公開的學位論文；(4)學位論文作者授權學校向中國科技信息研究所及其萬方數(shù)據(jù)電子出版社和中國學術期刊(光盤)電子出版社提交規(guī)定范圍的學位論文及其電子版并收入相應學位論文數(shù)據(jù)庫，通過其相關網站對外進行信息服務。同時本人保留在其他媒體發(fā)表論文的權利。非公開學位論文，保密期限內不向

3、外提交和提供服務，解密后提交和服務同公開論文。論文電子版提交至校圖書館網站：http：／／202．113．20．163：8001／index．htm。本人承諾：本人的學位論文是在南開大學學習期間創(chuàng)作完成的作品，并已通過論文答辯：提交的學位論文電子版與紙質本論文的內容一致，如因不同造成不良后果由本人自負。本人同意遵守上述規(guī)定。本授權書簽署一式兩份，由研究生院和圖書館留存。作者暨授權人簽字：董扛蕓2013年06月06日南開大學研究生學位論文作者信息論文題目圖的彩虹連通數(shù)的若干上界2013年05月30姓名董九英學號l120100012答辯日期日論文類別博士、『學歷碩士口碩

4、士專業(yè)學位口高校教師口同等學力碩士口院／系／所組合數(shù)學中心專業(yè)應用數(shù)學聯(lián)系電話13821061391Emailjiuyingdong@126．com通信地址(郵編)：4備注：是否批準為非公開論文注：本授權書適用我校授予的所有博士、碩士的學位論文。由作者填寫(一式兩份)簽字后交校圖書館，非公開學位論文須附《南開大學研究生申請非公開學位論文審批表》。南開大學學位論文原創(chuàng)性聲明本人鄭重聲明：所呈交的學位論文，是本人在導師指導下進行研究工作所取得的研究成果。除文中已經注明引用的內容外，本學位論文的研究成果不包含任何他人創(chuàng)作的、己公開發(fā)表或者沒有公開發(fā)表的作品的內容。對本論文

5、所涉及的研究工作做出貢獻的其他個人和集體，均已在文中以明確方式標明。本學位論文原創(chuàng)性聲明的法律責任由本人承擔。學位論文作者簽名：——董九英2013年06月06日非公開學位論文標注說明(本頁表中填寫內容須打印)根據(jù)南開大學有關規(guī)定，非公開學位論文須經指導教師同意、作者本人申請和相關部門批準方能標注。未經批準的均為公開學位論文，公開學位論文本說明為空白。論文題目申請密級口限制(≤2年)口秘密(≤10年)口機密(420年)保密期限20年月日至20年月日’審批表編號批準日期20年月日南開大學學位評定委員會辦公室蓋章(有效)注：限制★2年(可少于2年)：秘密★10年(可少于1

6、0年)：機密★20年(可少于20年)中文摘要令G=(y(G)，E(G))是一個簡單無向有限圖，其中v(c)是G的頂點集，E(G)是G的邊集。在2006年，Chartrand等人引進了一種關于彩虹邊著色的新概念。其定義如下：G的一個k邊著色是一個映射C：E(G)--+C，其中c是k種不同顏色的集合。令G是一個邊著色圖。如果G中一條路的每條邊都著有不同的顏色，我們稱這條路為G的彩虹路。如果G的任意兩個頂點間都存在一條彩虹路連通它們，我們稱G為彩虹連通。如果一個邊著色使G彩虹連通，那么我們稱該著色為彩虹著色。我們把G的彩虹著色所需的最小顏色數(shù)稱為G的彩虹連通數(shù)，記為rc(

7、G)。從彩虹連通的定義，我們能看到一個彩虹連通圖的兩條相鄰的邊可以著相同的顏色。以上的著色定義在一個圖的邊集上，自然地，我們可以把以上的著色推廣到圖G的頂點集上。在2008年，Krivelevich和Yuster引進了彩虹點著色的概念，類似地給出了點彩虹著色、點彩虹路、點彩虹連通，點彩虹連通數(shù)rvc(G1的定義。根據(jù)rc(G1和rvc(G)的定義，Chartrand等人計算出了一些特殊圖類的彩虹連通數(shù)。然而，對于一般圖來說，計算它們的彩虹連通數(shù)是一件非常困難的事情。Chakraborty等人證明：對于一個給定的圖G，確定rc(G)是否等于2是ⅣP一完全的。特別地