【正文】 是針對(duì)，但是兩者之間較為接近的情況進(jìn)行的一個(gè)討論。因此，研究這類(lèi)的新輪圖是有一定意義的。為說(shuō)明情況，給出一個(gè)的新輪圖，如圖所示，圈，有個(gè)內(nèi)部頂點(diǎn)，所以彩虹連通數(shù)，就是說(shuō)這個(gè)圖只需要中顏色進(jìn)行染色，就可以使得圖中任意兩個(gè)頂點(diǎn)之間至少有一條彩虹路相連，即圖是彩虹連通的。另一方面，要使圖中，任意兩個(gè)頂點(diǎn)之間至少有一條彩虹路相連，種顏色就已經(jīng)滿足染色需求，不需要多一種的顏色。斷言這種情況下的彩虹連通數(shù)應(yīng)是，假設(shè)，那么對(duì)于內(nèi)部的個(gè)頂點(diǎn)而言，會(huì)使得其中某些頂點(diǎn)之間沒(méi)有彩虹路相連，比如說(shuō)頂點(diǎn)和，之間連接的邊染了同種顏色，就沒(méi)有彩虹路。因此，彩虹連通數(shù)。情況：圈上的頂點(diǎn)數(shù)少于內(nèi)部頂點(diǎn)數(shù)相同，即。按照上述的染色方法，能夠保證任意兩個(gè)內(nèi)部頂點(diǎn)和，之間至少存在一條彩虹路相連，圈上的邊的染色需要的顏色完全可以取自種顏色，并且不需要取全部的種顏色就能使得在圖中，任意兩個(gè)頂點(diǎn)之間至少有一條彩虹路相連。類(lèi)似的，對(duì)于個(gè)內(nèi)部頂點(diǎn)，要保證個(gè)內(nèi)部頂點(diǎn)中，任意兩個(gè)頂點(diǎn)之間有一條彩虹路相連，則需要的顏色數(shù)為。可以看出，個(gè)內(nèi)部頂點(diǎn)之間存在一條最短的路，且，于是決定將此條路染色成彩虹路，因此邊分別染，這樣的染色方法確保了個(gè)內(nèi)部頂點(diǎn)之間的最短路徑是一條彩虹路。為了敘述簡(jiǎn)潔，給出一個(gè)的新輪圖，如圖所示，圈，并有的內(nèi)部頂點(diǎn)?？紤]新輪圖，一個(gè)階的圈，還有個(gè)頂點(diǎn)連接圈的每個(gè)頂點(diǎn)，且這個(gè)頂點(diǎn)之間沒(méi)有邊直接相連，這樣構(gòu)成的圖就是新輪圖。于是。類(lèi)似的，使得。由于，于是。現(xiàn)在，做一個(gè)相反的假設(shè)，同樣定義輪圖的一個(gè)彩虹染色，并假設(shè)。接下來(lái)，我們證明。定義一個(gè)邊染色如下：如果是奇數(shù)，則；如果是偶數(shù)，則；對(duì)于每個(gè)，有。可以驗(yàn)證這樣的一個(gè)邊染色就是一個(gè)彩虹染色，因此。再考慮，當(dāng)時(shí)，輪圖不再是一個(gè)完全圖，于是。首先考慮，當(dāng)時(shí)。在推導(dǎo)新輪圖的彩虹連通數(shù)之前，讓我們先來(lái)看看輪圖的彩虹連通數(shù)，參考了文獻(xiàn)。當(dāng)然我們所研究的不僅僅是這樣的輪圖，而是圈中加入了個(gè)頂點(diǎn)的輪圖，并且給出輪圖的彩虹連通數(shù)和證明。輪圖是一個(gè)有個(gè)內(nèi)部頂點(diǎn)，個(gè)葉子頂點(diǎn)，且被一個(gè)圈連接的圖，根據(jù)圖的定義，可知輪圖是一個(gè)特殊的圖，最小度。首先定義圈，其邊為。做一個(gè)簡(jiǎn)單的計(jì)算，可以得到：，當(dāng)時(shí)。這里的指的是連通圖中的頂點(diǎn)數(shù)，于是，我們可以計(jì)算下圖中的頂點(diǎn)數(shù)，即，是層數(shù)。綜上所述，很容易推出：?，F(xiàn)在，我們已經(jīng)證明了。于是，我們有：這就和的極大性矛盾了。路徑的前部分條邊染色是全部不相同的，路徑的后部分條邊中相同序號(hào)的顏色是重復(fù)的。如果是奇數(shù)，那么我們可以使路徑的條邊染色，需要種新顏色。路徑的前半部分染色是全部不相同的，路徑的后半部分相同序號(hào)的顏色是重復(fù)的。我們可以把頂點(diǎn)加入中，從而構(gòu)成一個(gè)更大的子圖，它有個(gè)頂點(diǎn)。不失一般性，我們假設(shè)，且。而且，其中的所有頂點(diǎn)都滿足上述的屬性，我們選擇頂點(diǎn)使得三條路徑的其中一條長(zhǎng)度為，比如說(shuō)，而使路徑和的長(zhǎng)度之和盡可能大。那么我們對(duì)的選擇有了矛盾。我們可以把這四個(gè)頂點(diǎn)加入圖中，從而形成一個(gè)更大的子圖，它有個(gè)頂點(diǎn)。接下來(lái)，假設(shè)，在的外部有四個(gè)不同的頂點(diǎn)，分別是，并且它們有三條內(nèi)部不相交的路徑到，進(jìn)一步假設(shè)，這四個(gè)頂點(diǎn)，每三個(gè)頂點(diǎn)時(shí)相鄰的。如果，是圖的一個(gè)子圖，令，那么。證明：假設(shè)存在這樣一個(gè)是圖的一個(gè)最大連通子圖，并且滿足，其中是圖的頂點(diǎn)數(shù)。接下來(lái)，我們將對(duì)連通度為的彩虹連通數(shù)的上界做出改善，即。等人證明了，如果連通度為，那么彩虹連通數(shù)。然后，等人認(rèn)為這樣的結(jié)果并不令人滿意，于是改善了和的關(guān)于彩虹連通數(shù)的上界，即，并且證明了對(duì)于所有階數(shù)為，最小度為的連通圖都是適用的。和利用階支配集的方法，證明了有個(gè)頂點(diǎn)，最小度為的連通圖的彩虹連通數(shù)為。但是，利用這個(gè)上界驗(yàn)證之前，在它的基礎(chǔ)上對(duì)于這個(gè)上界做了一些改善，使得更為緊一些，即，再以改善后的這個(gè)上界來(lái)驗(yàn)證本文的結(jié)論。在文獻(xiàn)中，現(xiàn)有的關(guān)于連通圖的彩虹連通數(shù)只是一個(gè)上界，即，階為，最小度為?；蛟S，還存在比本文更優(yōu)的一種染色方法，使得最后得到更優(yōu)的彩虹連通數(shù)，由于知識(shí)水平有限，本文就不會(huì)進(jìn)一步研究了。在這樣的圖中，對(duì)于一些層數(shù)較少的，比如的圖，可以通過(guò)簡(jiǎn)單的邊染色方法，就能計(jì)算出其彩虹連通數(shù)，并且彩虹連通數(shù)會(huì)少于由式子計(jì)算出的彩虹連通數(shù)。因此，無(wú)論哪種情況，此種染色方法得到的圖都能滿足，圖中任意兩個(gè)頂點(diǎn)之間至少有一條彩虹路相連。因?yàn)樘卣鳂?shù)上的邊的染色是取用新的顏色，結(jié)合情況，我們也很容易知道，任意兩個(gè)頂點(diǎn)之間至少有一條彩虹路連接；情況：圖中任取的兩個(gè)頂點(diǎn)位于不同的一個(gè)子圖和中。情況：圖中任取的兩個(gè)頂點(diǎn)恰巧位于同一個(gè)子圖中。這樣得到的一個(gè)邊染色可驗(yàn)證此時(shí)是彩虹連通的，邊染色所用的顏色數(shù)為，因此。將所有這樣的子圖用上述的方法進(jìn)行染色，共使用七種顏色，而伴隨圈上未染色的邊可選取中的任意一種顏色對(duì)其進(jìn)行染色。這樣的圖是彩虹連通的，因此。層數(shù)為的圖正如圖所示，顯然，這是一個(gè)完全圖，因此，彩虹連通數(shù)為。這樣就得到了層的圖的一種邊染色方法，使用了十六種顏色，可以驗(yàn)證，在這種染色方法下，圖是彩虹連通的，因此。此時(shí)，伴隨圈上還有一些邊未染色，我們選取中的任意一種顏色對(duì)其進(jìn)行染色，比如說(shuō)，我們選取了顏色對(duì)這些邊進(jìn)行染色。這個(gè)子圖還剩余4條邊未染色，于是我們給著四條邊染，這樣的染色，子圖便使用了七種顏色。比如，所示的圖，這是一個(gè)層的圖，含有與相連的結(jié)點(diǎn)構(gòu)成的七個(gè)頂點(diǎn)的子圖，即?？紤]了度為，有層的圖的這些特點(diǎn)以后，我們可以這樣對(duì)其進(jìn)行邊染色。對(duì)一個(gè)度為，有層的圖，記第（）層為，其總的頂點(diǎn)數(shù)為。對(duì)于這樣的圖，我們可以看到，每個(gè)內(nèi)部結(jié)點(diǎn)的度為，并且只有一個(gè)根結(jié)點(diǎn)，為了簡(jiǎn)化敘述，可以把根結(jié)點(diǎn)記作，把根結(jié)點(diǎn)外一層記作第一層，依次往外是第二層、第三層等等。第一節(jié) 度數(shù)為的圖的彩虹連通數(shù)上面已經(jīng)給出了圖的定義，我們要研究是頂點(diǎn)度數(shù)為的一類(lèi)特殊圖。在文獻(xiàn)中，作者證明了：（找出哪篇文章里得到的這個(gè)結(jié)果）要計(jì)算出任意的一個(gè)圖的彩虹連通數(shù)是一個(gè)困難的問(wèn)題。這樣得到的圖被稱作圖，樹(shù)叫做特征樹(shù)，圈叫做伴隨圈。接下來(lái)，首先了解，什么樣的圖是圖，在這里給出其定義：定義 在平面上嵌入一棵樹(shù)，的每個(gè)內(nèi)部頂點(diǎn)的度數(shù)至少為3，并且至少有一個(gè)內(nèi)部頂點(diǎn)。定理令是大?。旤c(diǎn)數(shù)）為的非平凡連通圖，即圖的階為，則有：；，是完全圖；，是一棵樹(shù)；，是頂點(diǎn)數(shù)的圈。參考文獻(xiàn)，作者證明了對(duì)于任意的連通圖的彩虹連通數(shù)的上界，即，利用這個(gè)結(jié)論證明度數(shù)為的圖的彩虹染色方法是有意義的；參考了文獻(xiàn)，推導(dǎo)出了新輪圖的彩虹連通數(shù)；參考了文獻(xiàn)，從連通圖推導(dǎo)出圖是一個(gè)連通的串并聯(lián)圖，進(jìn)一步根據(jù)連通串并聯(lián)圖，最后得到了考慮廣義圖，并且本文對(duì)廣義圖進(jìn)行彩虹染色，得到了彩虹連通數(shù)。通過(guò)上述的例子，我們已經(jīng)初步了解到圖的彩虹染色，彩虹連通數(shù)等概念，本文針對(duì)三類(lèi)特殊的圖進(jìn)行彩虹染色，并且給出了彩虹連通數(shù)的一個(gè)上界。因此，確定。又得考慮，如果，那么在這種染色下，圖中沒(méi)有彩虹路；如果，那么在這種染色下，圖中沒(méi)有彩虹路。接下來(lái)，考慮兩種情況：情況，那么，在這種染色下，圖中沒(méi)有彩虹路。接下來(lái)，考慮其它邊的染色，首先，如果和是圖的任意兩個(gè)頂點(diǎn)，并且，那么在圖中僅有一條長(zhǎng)度為的路，而其它所有的路的長(zhǎng)度是或者更大，因此，這就說(shuō)明在圖中沒(méi)有兩條相鄰的邊染色是相同的。現(xiàn)在，假設(shè)，正如圖所示，在圖中的條路中至少有