【正文】 令 xuuauP s?211 ? ， bvvxvP t?212 ? ，其中Hba ?, ，對于所有的 i 和 j ， Hvu ji ?, 。 說明 )( xGrc 是有意義的： 上面我們已經(jīng)按照定義的染色方法推出了，度為 3 ，層為 3?k ，頂點數(shù)為 n的 Halin 圖的彩虹連通數(shù) 423)( 2 ??? ?kkGrc ，然后，我們又對 ?3 連通圖的彩虹連通數(shù)的上界進(jìn)行的改善，得到了一個更好的上界，即 5 )1(3)( ?? nGrc 。定義一個 ?2 邊染色 }2,1{)(: ?nWEc 如下：如果 i 是奇數(shù)，則 1)( ?vvc i ， 1)( 1 ??iivvc ；如果 i 是偶數(shù)，則 2)( ?vvc i ， 2)( 1 ??iivvc 。 對新輪圖 knW? 進(jìn)行染色，因為 k 個內(nèi)部頂點 kuuu ?, 21 之間沒有直接的邊連接，為了確保內(nèi)部頂點之間至少有一條彩虹路連接，所以先考慮 k 個內(nèi)部頂點之間的彩虹路。這點可以從一個簡單的例子進(jìn)行說明。接下來，我們給出彩虹 ?k 連通數(shù) )(Grck 的定義：若存在圖 G 的一個邊染色，使用 t 種顏色就能夠使得圖 G 彩虹 ?k 連通，其中 t 是最小的整數(shù)，那么彩虹 ?k 連通數(shù)為：tGrck ?)( 。類似的，對于)3( ，如果 X 和 Y 相交，那么一條適合的路徑是一個點，這點在 YX? 中。假設(shè)路徑是 l ,1? ，1)()( 1 ??? lQeQe ? 。 F 的其余的邊染不同的新的顏色。定義廣義 ?? 圖：令qtqG ,1??? ，它是 2?t 的路徑的集合，路徑的長度 11 ??? tqq ? ，其中 21??tq ，并且路勁上的每對內(nèi)部頂點時不相交的，而且都有兩個相同的端點。 對于每個 i 重復(fù)，直到 GGt? 。路徑 iQ 的邊染色映射到端點 x 和 y ，分別染色 i 和 1?i ，其中 11 ??? ti 。我們都知道，一個圖是圈的話，它的彩虹連通數(shù)是 ??????? 2)( nCrc n，如果從圈的角度來驗證，圖 YX ??? 21 的彩虹連通數(shù)是滿足的。 如果路徑 t ,1 ? 的頂點數(shù)分別是： tkk ,1? ，且 nkk t ????1 ，那么彩虹連通數(shù) ?????? ?????????? ???? ? 1212)( 121 tt kkkkrc ?， nkk t ????1 。 本文選取這三類特殊圖進(jìn)行彩虹染色，也得到了相應(yīng)的彩虹連通數(shù) )(Grc ，或許本文的染色方法并不是最優(yōu)異的，得到的彩虹連通數(shù) )(Grc 也不是最小的，這點是由于知識水平的有限，不能做到最優(yōu)秀，還望閱讀過本文的讀者給予意見，我會進(jìn)一步改善染色方法，得到更優(yōu)的彩虹連通數(shù)。利用改善后的 ?3 連通圖的彩虹連通數(shù) 5 )1(3)( ?? nGrc 說明了 )( xGrc 是有意義的。而按照本文的染色方法得到的彩虹連通數(shù)是 10)( ??rc ，少于計算出的彩虹連通數(shù)，所以本文的給出的針對廣義 ?? 圖的染色方法可以減少所使用的顏色數(shù)，是有意義的染色方法。此時要選取長度較長的一條進(jìn)行染色，于是選取以順時針的一條染色，分別染 色色，色，色，色， 54321 。 首先，因為 2)( ??? nyGe ，如果給圖 G 染色，少于 2?n 種顏色，那么對于某些頂點}{ )(, xyvu ??，在 yG? 中存在唯一的 vu? 路徑 P 不是彩虹路。加入的 iQ 和方向同上面方法一樣。這就完成了定理 5 的 XXIII 證明，因此定理 4 也就成立了。 情況 3 ： 2)( 2 ?Qe 。 接下里，先對每個 iH 定義一個邊染色。那么這樣的 ?2 連通圖就是一個著名的亞族。 第三節(jié) 特殊圖類，廣義 ?? 圖的彩虹連通數(shù) 在討論廣義 ?? 圖之前，我們先來了解幾個定義。 XVIII 情況 3 ：圈 nC 上的頂點數(shù)多余于內(nèi)部頂點數(shù) k ，即 kn? 。因為 2)( 2 ?vvc 和 2)( 5 ?vvc ，從而在圖 nW 中路徑 52 vv? 不是一條彩虹路，這就產(chǎn)生了矛盾。 定理 .3 當(dāng) 3?n 時，輪圖 nW 的彩虹連通數(shù)是： ??????????.73,642,31)(nnnWrc n若若若 證明：假設(shè)有一個 n 階的圈 1121 ,: vvvvvC nnn ??? ，還有一個頂點 K 連接 圈nC 的每個頂點構(gòu)成的圖稱為輪圖 nW 。因此，我們只要假設(shè) 21 ??? ts ?，F(xiàn)在進(jìn)行染色，只使用兩種新的顏色 1色和 2 色對 12條邊進(jìn)行染色，使用 1色對邊 1if ， 3,2,1?i 進(jìn)行染色，使用 2 色對其它的 9 條邊進(jìn)行染色。 現(xiàn)在，我們開始說明這個上界改善的合理性，參考文獻(xiàn) ]12[ ： 在圖染色理論中，有一些方法是通過圖 G 的最小度 )(G? 來研究圖的彩虹連通數(shù) )(Grc 的， Caro 等人證明了，如果圖 G 是一個階數(shù)為 n ，最小度為 ? 的連通圖，那么圖 G 的彩虹連通數(shù)為 })3ln4()),1(1()lnm i n { ()( ???? ? nonGrc ??? 。至此， kG的特征樹中未染色的邊的數(shù)目為 323 2?? ?k ，于是我們可以使用新的 323 2?? ?k 種顏色對這些邊進(jìn)行染色。圖 3 所示的是第四層有 24 個頂點（葉子頂點），總的頂點數(shù)為 46?n 的 Halin 圖。對于彩虹連通數(shù)，定理 1給出了 Chartrand 等人對于圖 G 是完全圖，或是一棵樹，或 是一個圈的彩虹連通數(shù)，這個定理對于本文研究的第一類特殊圖，度數(shù)為 3 的 Halin 圖的彩虹染色有相應(yīng)地運用。由于圖 P 中任意兩個不相鄰頂點之間有且僅有一條長度為 2 的路，而 u 和 v 之間的 2長路 uwv 不是一條彩虹路，故 u 和 v 之間沒有彩虹路相連，這與 c 是圖 P 是一個彩虹 ?2 染色的假設(shè)相矛盾。其中，最簡單的 2連通圖是圈 ，并且其它的 2連通圖都可以由一個圈通過不斷添加路而得到。 有圖必然會有由 G 產(chǎn)生而來的別的圖，這里只介紹子圖的概念。事實上，政府機構(gòu)之間需要進(jìn)行一些機密信息的傳遞，這些傳輸要保證其安全性，于是便產(chǎn)生了彩虹連通的這些概念。同樣，圖的染色在許多領(lǐng)域都會涉及到將某種對象的集合按照一定的規(guī)則進(jìn)行分類，比如說，學(xué)生選課系統(tǒng)、電路布局、排序問題、會議安排、電路安排、考試安排等，這些問題都與圖的染色理論密切相關(guān)，專家學(xué)者對圖的不同染色問題的研究，已經(jīng)有了較為 豐富的結(jié)果，并且這些結(jié)果仍在進(jìn)一步完善中。而自環(huán)是指兩端連接著同一頂點的邊。連通度是指，使得圖 G 是 ?k 連通的最大整數(shù) k ，記作 )(G? 。故Petersen 圖 P 的 3邊染色 c 是一個彩虹染色，從而 3)( ?Prc 。因此，確定 4)( ?Grc 。 對于這樣的 Halin 圖 G ，我們可以看到，每個內(nèi)部結(jié)點的度為 3 ，并且只有一個根結(jié)點，為了簡化敘述，可以把根結(jié)點記作 0v ，把根結(jié)點外一層記作第一層， VIII 依次往外是第二層、第三層等等。這樣的 Halin 圖 2G 是彩虹連通的，因此 X 6)( 2 ?Grc 。在文獻(xiàn) ]12[ 中，現(xiàn)有的關(guān)于 ?3 連通圖的彩虹連通數(shù)只是一個上界，即 313)( ??? ? nGrc ，階為 n ，最小度為 ? 。 接下來，假設(shè) 3??nh ，在 H 的外部有四個不同的頂點，分別是 4321 , xxxx ，并且它們有三條內(nèi)部不相交的路徑到 H ，進(jìn)一步假設(shè)，這四個頂點，每三個頂 XIII 點時相鄰的。路徑的前部分 2 1??ts 條邊染色是全部不相同的，路徑的后部分 2 1??ts 條邊中相同序號的顏色是重復(fù)的。當(dāng)然我們所研究的不僅僅是這樣的輪圖，而是圈中加入了 k 個頂點的輪圖 kn KC? ，并且給出輪圖 knW? 的彩虹連通數(shù)和證明。由于 2)( 4 ?vvc ，于是 1)( ?vvc n 。 情況 2 ：圈 nC 上的頂點數(shù)少于內(nèi)部頂點數(shù) k 相同，即 kn? 。比方說，圈 nC 中 3?n ，而內(nèi)部頂點數(shù) 500?k ，按照本文的染色方法，就需要 500 種顏色才能使得圖 5003?W 彩虹連通，即500)( 5003 ??Wrc ，對于這類的圖，雖然可以計算出彩虹連通數(shù)，但是失去了圖的彩虹染色的意義，在實際的應(yīng)用中，我們對于這樣兩方相差懸殊，必定會對少的一方做一些補充，否則投入成本過大，這也就失去了實際應(yīng)用的意義。本文會提供一種新的染色方法，使得廣義 ?? 圖是彩虹連通的，并且彩虹連通數(shù) )(Grc 小于2?n 。重復(fù)這個過程，直到結(jié)束。 彩虹染色 1Q 使用的顏色為 lFVmm ??? )(,1 ? 。對于 )1( 歸納假設(shè)，如果 )(, 1?? iHVvu 。如果增加的路徑 jQ 是以1?jG 外部為導(dǎo)向，那么 iQ 導(dǎo)向使得， z 任然在 iG 新的外部圈中。 完成了 ?2 連通串并聯(lián)圖 G ，最后考慮廣義 ?? 圖， 參考了文獻(xiàn) ]18[ ： 定理 .8 如果 qtqG ,1??? 是一個廣義 ?? 圖，頂點數(shù) 為 n ，那么 ??? ????? 3,21 2,)(2 tnntnGrc 或 定理 8 證明：假設(shè) t ,1? 是 t 條路徑， yx, 是 t 條路徑的共同的端點。路徑 1Q 上有 3個頂點， 321 , vvv ，有 4 條邊；路徑 2Q 上有 4 個頂點， 4321 , uuuu ，有 5 條邊。按照上面的推廣，如果 3Q 的頂點數(shù)變?yōu)?3k ， 4Q 的頂點數(shù)變?yōu)?4k ，那么對于圖 YX ??? 43 還是采用上述的方法進(jìn)行彩虹染色，于是彩虹連通數(shù)是： ?????? ?????? 12)( 4343 kkYXrc。22)(21是奇數(shù)且是偶數(shù)且，tttjiktkktttjitkktkkrctjiji 其中， n 個頂點是指不計算端點 X 和 Y ，只是 t 條路徑上頂點的總數(shù)，即ji kkn ?? ， tji ???2 。 [10],et al. On rainbow connection. Electron J Combin 15, R57 (2020)。這里的問題只是在于還有一條單一 的路徑 tQ ，我們只需要使得這條路徑是一條彩虹路，就能夠保證整個廣義 ?? 圖彩虹連通。采取相同的染色方法，考慮圖 YX ??? 43 ，如圖 9 所示，圖上總的有 10條邊，考慮最遠(yuǎn)的兩個頂點（端點 X 和 Y 不作為首先考慮的頂點）， 2v 和 3u ，形成了兩條 32 uv? 路，順時針的一條，即 34432 , uuvvv ，長度為 5 ，逆時針的一條，即 32112 , uuuvv ，長度也為 5 。因此， 1)(2 ??nGrc 。首先， 0G 是彩虹染色，使用了 )( 0GV中顏色。 iG 是從 1?iG 附加一條長度至少為 1的路徑 iQ 到 1?iG 得到的， ti??1 ，用兩個不同的頂點 )(, 1?? iGVyx 來辨別路徑 iQ 的末端點。歸納證明了，對于 iH 的染色滿足所有的需求， ti??0 。分別把 jQ的第一條邊和最后一條邊射入到 iv 和 j? 。對于任意的頂點 )(GVu? 和任意集合 )( uGVX ?? ， kX? ，這里有從 u 到 X 的 k 條路徑，使得對于其中的任意兩條路，僅僅只有一個共同頂點 u 。因此，前面定義的 )(Grck 僅僅是針對 ?k 連通圖而言的。因此，研究這類的新輪圖knW? 是有一定意義的。 可以看出， 8 個內(nèi)部頂點之間存在一條最短的路 ji KvK ?? ， }8,2,1{, ??ji 且ji? ，于是決定將此條路染色成彩虹路，因此邊分別染 色，色，色， 821 ??vK i ，8,2,1 ??i ，這樣的染色方法確保了 8 個內(nèi)部頂點之間的最短路徑 ji KvK ?? 是一條彩虹路。定義一個 ?3 邊染色 }3,2,1{)(: ?nWEc 如下：如果 i 是奇數(shù)，則 1)( ?vvc i ；如果 i 是偶