【正文】 。相應地，其它的五個子 圖使用相同的染色方法，同樣只需要 }7,6,5,4,3,2,1{ 七種顏色。接下來，我們考慮剩余的未 染色的特征樹上的邊，對于這些邊我們選取新的顏色對其進行染色，比如說，分別染 16,15,14,13,12,11,10,9,8, ，共九種顏色。 IX 圖 3 4 層的 Halin 圖 4G 接下來，我們考慮其它層數(shù) k 的 Halin 圖，并且推導出了其彩虹連通數(shù))( xGrc ： 情況 1：當 1?k 時，則有 1)( 1 ?Grc 。 圖 1?k 的 Halin 圖 情況 2 ：當 2?k 時 層數(shù)為 2 的 Halin 圖如圖 所示，可以看到，三個子圖 210 , HHH 是一個三角形的完全圖，于是我們可以分別染 3,2,1 顏色，伴隨圈 nC 中未染色的邊可以染 1，特征樹中未染色的邊分別染 6,5,4 色。 圖 2?k 的 Halin 圖 情況 3：當 3?k 時 我們的染色方法同 4?k 時的 Halin 圖的染色方法相同， k 層的 Halin 圖 kG 的頂點數(shù) 223 ??? kn ，圖 kG 中包含了 323 ??k 個（ nC 與相連的結點構成的七個頂點）的子圖。至此， kG的特征樹中未染色的邊的數(shù)目為 323 2?? ?k ，于是我們可以使用新的 323 2?? ?k 種顏色對這些邊進行染色。 進一步說明此種染色方法得到的 Halin 圖是彩虹連通的。因為我們采取的邊染色方法已經(jīng)使得子圖 iH 是彩虹連通的，所以，任意兩個頂點之間至少有一條彩虹路連接；情況 2 ：圖 xG 中任取的兩個頂點其中一個位于同一個子圖 iH 中，3230 ???? ki ，另一個位于特征樹上（不包含子圖中的頂點）。 因為一個子圖中任意一個頂點有三條邊連接，所以這樣的兩個頂點之間有許多條路連接，只要確保這條路徑在子圖 iH 和 jH 中邊的顏色不同，那么這條路一定是彩虹路，也就是說任意兩點之間至少有一條彩虹路連接。 綜上所述，當 1?k 時， 1)( 1 ?Grc ；當 2?k 時， 6)( 2 ?Grc ；當 3?k 時，423)( 2 ??? ?kkGrc 。因此，本文需要再次聲明，采取的染色方法是較為保守的，但是確保了這種的染色方法，一定使得圖 kG 中任意兩個頂點之間至少有一條彩虹路相連，是滿足了讓圖 kG 彩虹連通。 要證明所推出的度為 3 ，層為 x ，頂點數(shù)為 n 的 Halin 圖的彩虹連通數(shù) )( xHrc的合理性，本文從 ?3 連通圖的彩虹連 通數(shù)的角度進行說明。 并且這個上界是針對所有的 ?3 連通圖而言的，而本文驗證的是一個特殊的 ?3 連通圖，它的所有頂點的度為 3 ，即 3?? ， 343)( ?? nGrc 。 現(xiàn)在，我們開始說明這個上界改善的合理性，參考文獻 ]12[ ： 在圖染色理論中，有一些方法是通過圖 G 的最小度 )(G? 來研究圖的彩虹連通數(shù) )(Grc 的， Caro 等人證明了，如果圖 G 是一個階數(shù)為 n ，最小度為 ? 的連通圖，那么圖 G 的彩虹連通數(shù)為 })3ln4()),1(1()lnm i n { ()( ???? ? nonGrc ??? 。而 rSchiermeye 證明了，對于最小度為 3 的圖 G ，即 3?? ，那么它的彩虹連通數(shù)為 43)( nGrc ? 。 rSchiermeye 已經(jīng)證明了，如果圖 G 是一個 n 階，連通度 1)( ?Gk ，最小度3?? ，那么彩虹連通度 4 13)( ?? nGrc 。從 Chandran 等人的結論中，我們能夠容易推出彩虹連通數(shù)的一個上界： 31)( 3313)( ?????? Gk nnGrc ? 因此，對于連通度 3)( ?Gk ，彩虹連通數(shù) 343)( ?? nGrc ，連通度 4)( ?Gk ，彩虹連通數(shù) 353)( ?? nGrc 。 定理 .2 如果圖 G 是一個 n 個頂點的 ?3 連通圖，那么 5 )1(3)( ?? nGrc 。 如果，圖 G 中含有一個三角形 3C ，令 3CH? ，那么 581)(3 ??Crc。如果，在圖 G 中包含的所有圈的長度為 5 ，那么可以令 H 為包含增加一條側邊 5C 的圖，顯然，當 6?h 時， 5173)( ??Hrc 。令邊 ijf 映射到頂點 ix ， 3,2,1?j ?，F(xiàn)在進行染色，只使用兩種新的顏色 1色和 2 色對 12條邊進行染色，使用 1色對邊 1if ， 3,2,1?i 進行染色，使用 2 色對其它的 9 條邊進行染色。 515 )4(3251532)()( ????????? hhHrcHrc 這就說明了至少其中有四個頂點，例如 x ，有這樣的屬性，其中的三條內(nèi)部不相交 ?),( Hx 路徑 210 , PPP 的長度至少是 2 。令 xuuauP s?211 ? ， bvvxvP t?212 ? ，其中Hba ?, ，對于所有的 i 和 j ， Hvu ji ?, 。進一步，先假設 3??ts 。如果 ts? 是偶數(shù)，那么我們可以使路徑 bvvxvuuau ts ?? 2121 的 2??ts 條邊染色，需要 2 2??ts 種新顏色。我們對邊 0e 的染色可以選擇 H 中已經(jīng)重復的 任意一種顏色，那么這就簡單驗證了 H? 是彩虹連通的。路徑的中間部分的邊和邊 0e 使用 H中已經(jīng)使用過的任意一種顏色進行染色。這就證明了H? 是彩虹連通的。因此，我們只要假設 21 ??? ts 。 如果 3??nh ，那么 5 )1(32515 )3(32)()( ???????? nhHrcGrc ； XIV 如果 2??nh ，那么 5 )1(32515 )2(32)()( ???????? nhHrcGrc ； 如果 1??nh ，那么 5 )1(31515 )1(31)()( ???????? nhHrcGrc 。 說明 )( xGrc 是有意義的： 上面我們已經(jīng)按照定義的染色方法推出了，度為 3 ，層為 3?k ，頂點數(shù)為 n的 Halin 圖的彩虹連通數(shù) 423)( 2 ??? ?kkGrc ，然后，我們又對 ?3 連通圖的彩虹連通數(shù)的上界進行的改善，得到了一個更好的上界，即 5 )1(3)( ?? nGrc 。這樣， )( xGrc 就關于層數(shù) k 的函數(shù)，423)( 2 ??? ?kkGrc ，而 )(Grc 也可變換為有關層數(shù) k 的函數(shù)， 5 329)( ??? xGrc 。 第二節(jié) 特殊圖類， k 個內(nèi)部頂點的輪圖 前面對輪圖做了大致介紹，這里需要做進一步說明。對于 3?n 的圈，在圈中加入一個頂點 1K ，使得 1K 與圈上的每個頂點連接，那么這樣的圖 1KCn? 就稱作輪圖 nW 。 在前面已經(jīng)證明了圈 nC 的彩虹連通數(shù) ??????? 2)( nCrc n，接下來也將給出輪圖 nW的彩虹連通數(shù)，并證明。 新輪圖 knW? 是一個有 k 個內(nèi)部頂點 kvvv , 21 ? ，但 k 個頂點之間沒有邊直接 XV 相連接，有 n 個葉子頂點，且被一個圈連接的圖，根據(jù) Halin 圖的定義，可知新輪圖 knW? 并不是一個特殊的 Halin 圖，但是它的特殊性值得研究，那么新輪圖knW? 的最小度 },2m in{ nk ??? 。 定理 .3 當 3?n 時，輪圖 nW 的彩虹連通數(shù)是： ??????????.73,642,31)(nnnWrc n若若若 證明：假設有一個 n 階的圈 1121 ,: vvvvvC nnn ??? ，還有一個頂點 K 連接 圈nC 的每個頂點構成的圖稱為輪圖 nW 。這時的輪圖是一個完全圖，因此 1)( 3 ?Wrc 。定義一個 ?2 邊染色 }2,1{)(: ?nWEc 如下：如果 i 是奇數(shù)，則 1)( ?vvc i ， 1)( 1 ??iivvc ；如果 i 是偶數(shù)，則 2)( ?vvc i ， 2)( 1 ??iivvc 。 最后考慮，當 7?n 時?？梢则炞C這樣的一個邊染色就是一個彩虹邊染色，于是 3)( ?nWrc 。因為 7?n 的 nW 不是一個完全圖，于是2)( ?nWrc 。對于每個 i ， 24 ??? ni ， ivvv ,1 是 nW 中的唯一的長度為 2 的 ivv?1 路，所以，對于 24 ??? ni ， 2)( ?? vvc i 。這就使得 2)( 3 ?vvc ，反過來使得 1)( 1 ??vvc n 。因為 2)( 2 ?vvc 和 2)( 5 ?vvc ，從而在圖 nW 中路徑 52 vv? 不是一條彩虹路，這就產(chǎn)生了矛盾。因此綜上， 3)( ?nWrc 。 對新輪圖 knW? 進行染色，因為 k 個內(nèi)部頂點 kuuu ?, 21 之間沒有直接的邊連接，為了確保內(nèi)部頂點之間至少有一條彩虹路連接，所以先考慮 k 個內(nèi)部頂點之間的彩虹路。為了便于觀看，只選取了圈 8C 上的一個頂點 v 與內(nèi)部 8 的頂點相連，同時省略了 8 個內(nèi)部頂點與圈 8C 上別的頂點之間的連接邊。至于 8 個內(nèi)部頂點與圈 8C 上別的頂點之間相連邊的顏色，也完全可以從 8 種顏色中取出，且遠遠滿足染色需要。 XVII 圖 5 88?W 的新輪圖 接下來結合圈 nC 考慮新輪圖 knW? 是彩虹連通的，可分三類情況進行討論： 情況 1：圈 nC 上的頂點數(shù)與內(nèi)部頂點 數(shù) k 相同，即 kn? 。因此，彩虹連通數(shù) kWrc kn ?? )( 。同情況 1類似，圈 nC 上的邊的染色需要的顏色完全可以取自 k 種顏色，且遠遠少于 k 種，就能夠滿足在圖 knW? 中，任意兩個頂點之間至少有一條彩虹路相連， k 種顏色就已經(jīng)使得圖 knW? 彩虹連通。 XVIII 情況 3 ：圈 nC 上的頂點數(shù)多余于內(nèi)部頂點數(shù) k ，即 kn? 。所以，假設不成立。這點可以從一個簡單的例子進行說明。 之前有說明 ，頂點數(shù) 8?n 的輪圖 8W 的彩虹連通數(shù)是 3)( 8 ?Wrc ，增加一個內(nèi)部頂點以后，可以使得彩虹連通數(shù)變?yōu)?2)( 28 ??Wrc 。 XIX 圖 6 28?W 的新輪圖 對上述的討論作補充說明： 情況 3 中的圈 nC 上的頂點數(shù)多余于內(nèi)部頂點數(shù) k 相同，即 kn? ， n 只是相對k 而言，數(shù)量多，而不是遠遠大于 k 。因為 n 遠遠大于 k 的這種情況屬于特例，某些情況下甚至找不到任何一種染色方法使得它彩虹連通，或者說它就不存在彩虹連通圖。 類似的，情況 2 中圈 nC 上的頂點數(shù)少于內(nèi)部頂點數(shù) k 相同，即 kn? ，只是針對 n 和 k 相差并不是很大的情況。 綜上所述，我們可以確定新輪圖 knW? 的彩虹連通數(shù)。 第三節(jié) 特殊圖類，廣義 ?? 圖的彩虹連通數(shù) 在討論廣義 ?? 圖之前，我們先來了解幾個定義。首先是彩虹 ?k 連通，如果一條路的邊分別染不同的顏色，那么這條邊染色路就是一條彩虹路。接下來，我們給出彩虹 ?k 連通數(shù) )(Grck 的定義：若存在圖 G 的一個邊染色，使用 t 種顏色就能夠使得圖 G 彩虹 ?k 連通，其中 t 是最小的整數(shù)，那么彩虹 ?k 連通數(shù)為：tGrck ?)( 。本文的概念定 義部分介紹了，一個圖 G 是 ?k 連通的，當且僅當任意兩個頂點之間是連通的，并且由 k 條內(nèi)部頂點不相交的路徑連通。 XX 我們繼續(xù)說明 )(Grck ，在參考文獻 ]18[ 中，對于 1?k ， Caro 等人證明了，如果圖 G 的階數(shù)為 n ，那么 32)( nGrc ? ，如果圖 G 是 ?2 連通的，即 2?k ，那么)(2)( nOnGrc ?? 。因此，如果圖 G 是 ?l 連通的，那么 313)( ??? l nGrc 。 參考了文獻 ]18[ 以后， 接下來的部分是從 ?l 連通圖，推及到 ?2 連通的串并聯(lián)圖，在推廣到廣義 ?? 圖，并且對它們的彩虹連通數(shù)做出