【文章內(nèi)容簡介】 顏色。路徑的中間部分的邊和邊 0e 使用 H中已經(jīng)使用過的任意一種顏色進(jìn)行染色。路徑的前部分 2 1??ts 條邊染色是全部不相同的，路徑的后部分 2 1??ts 條邊中相同序號的顏色是重復(fù)的。這就證明了H? 是彩虹連通的。于是，我們有： 515 )1(32 151532 1)()( ??????????? ??????????? ????? tshtshtsHrcHrc 這就和 H 的極大性矛盾了。因此，我們只要假設(shè) 21 ??? ts 。 現(xiàn)在，我們已經(jīng)證明了 3??nh 。 如果 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 。 綜上所述，很容易推出： 5 )1(3)( ?? nGrc 。 說明 )( xGrc 是有意義的： 上面我們已經(jīng)按照定義的染色方法推出了，度為 3 ，層為 3?k ，頂點(diǎn)數(shù)為 n的 Halin 圖的彩虹連通數(shù) 423)( 2 ??? ?kkGrc ，然后，我們又對 ?3 連通圖的彩虹連通數(shù)的上界進(jìn)行的改善，得到了一個(gè)更好的上界，即 5 )1(3)( ?? nGrc 。 這里的 n 指的是 ?3 連通圖中的頂點(diǎn)數(shù)，于是，我們可以計(jì)算下圖 xG 中的頂點(diǎn)數(shù)，即 223 ??? kn ， k 是層數(shù)。這樣， )( xGrc 就關(guān)于層數(shù) k 的函數(shù)，423)( 2 ??? ?kkGrc ，而 )(Grc 也可變換為有關(guān)層數(shù) k 的函數(shù)， 5 329)( ??? xGrc 。做一個(gè)簡單的 計(jì)算，可以得到： 5 329)(423)( 2 ??????? ? xkx GrcGrc ，當(dāng) Nkk ?? ,3 時(shí)。 第二節(jié) 特殊圖類， k 個(gè)內(nèi)部頂點(diǎn)的輪圖 前面對輪圖做了大致介紹，這里需要做進(jìn)一步說明。首先定義圈1121 , vvvvvC nnn ?? ?? ，其邊為 1?? iii ve ， ni??1 。對于 3?n 的圈，在圈中加入一個(gè)頂點(diǎn) 1K ，使得 1K 與圈上的每個(gè)頂點(diǎn)連接，那么這樣的圖 1KCn? 就稱作輪圖 nW 。 輪圖 nW 是一個(gè)有 1個(gè)內(nèi)部頂點(diǎn) 1K ， n 個(gè)葉子頂點(diǎn)，且被一個(gè)圈連接的圖，根據(jù) Halin 圖的定義，可知輪圖 nW 是一個(gè)特殊的 Halin 圖，最小度 3?? 。 在前面已經(jīng)證明了圈 nC 的彩虹連通數(shù) ??????? 2)( nCrc n，接下來也將給出輪圖 nW的彩虹連通數(shù)，并證明。當(dāng)然我們所研究的不僅僅是這樣的輪圖，而是圈中加入了 k 個(gè)頂點(diǎn)的輪圖 kn KC? ，并且給出輪圖 knW? 的彩虹連通數(shù)和證明。 新輪圖 knW? 是一個(gè)有 k 個(gè)內(nèi)部頂點(diǎn) kvvv , 21 ? ，但 k 個(gè)頂點(diǎn)之間沒有邊直接 XV 相連接，有 n 個(gè)葉子頂點(diǎn)，且被一個(gè)圈連接的圖，根據(jù) Halin 圖的定義，可知新輪圖 knW? 并不是一個(gè)特殊的 Halin 圖，但是它的特殊性值得研究，那么新輪圖knW? 的最小度 },2m in{ nk ??? 。 在推導(dǎo)新輪圖 knW? 的彩虹連通數(shù)之前，讓我們先來看看輪圖 nW 的彩虹連通數(shù)，參考了文獻(xiàn) ]7[ 。 定理 .3 當(dāng) 3?n 時(shí)，輪圖 nW 的彩虹連通數(shù)是： ??????????.73,642,31)(nnnWrc n若若若 證明：假設(shè)有一個(gè) n 階的圈 1121 ,: vvvvvC nnn ??? ，還有一個(gè)頂點(diǎn) K 連接 圈nC 的每個(gè)頂點(diǎn)構(gòu)成的圖稱為輪圖 nW 。首先考慮，當(dāng) 3?n 時(shí)， 43 KW? 。這時(shí)的輪圖是一個(gè)完全圖，因此 1)( 3 ?Wrc 。 再考慮，當(dāng) 64 ??n 時(shí)，輪圖 nW 不再是一個(gè)完全圖，于是 2)( ?nWrc 。定義一個(gè) ?2 邊染色 }2,1{)(: ?nWEc 如下：如果 i 是奇數(shù)，則 1)( ?vvc i ， 1)( 1 ??iivvc ；如果 i 是偶數(shù)，則 2)( ?vvc i ， 2)( 1 ??iivvc ?？梢则?yàn)證這樣的 一個(gè)邊染色就是一個(gè)彩虹染色，因此 2)( ?nWrc 。 最后考慮，當(dāng) 7?n 時(shí)。定義一個(gè) ?3 邊染色 }3,2,1{)(: ?nWEc 如下：如果 i 是奇數(shù)，則 1)( ?vvc i ；如果 i 是偶數(shù)，則 2)( ?vvc i ；對于每個(gè) )( nCEe? ，有 3)( ?ec ?？梢则?yàn)證這樣的一個(gè)邊染色就是一個(gè)彩虹邊染色，于是 3)( ?nWrc 。 接下來，我們證明 3)( ?nWrc 。因?yàn)?7?n 的 nW 不是一個(gè)完全圖，于是2)( ?nWrc ?，F(xiàn)在，做一個(gè)相反的假設(shè)， 2)( ?nWrc ，同樣定義輪圖 nW 的一個(gè)彩虹 ?2 染色 c? ，并假設(shè) 1)( 1 ?? vvc 。對于每個(gè) i ， 24 ??? ni ， ivvv ,1 是 nW 中的唯一的長度為 2 的 ivv?1 路，所以，對于 24 ??? ni ， 2)( ?? vvc i 。由于 2)( 4 ?vvc ，于是 1)( ?vvc n 。這就使得 2)( 3 ?vvc ，反過來使得 1)( 1 ??vvc n 。類似的， 1)( 1 ??vvc n XVI 使得 2)( 2 ?vvc 。因?yàn)?2)( 2 ?vvc 和 2)( 5 ?vvc ，從而在圖 nW 中路徑 52 vv? 不是一條彩虹路，這就產(chǎn)生了矛盾。于是 2)( ?nWrc 。因此綜上， 3)( ?nWrc 。 考慮新輪圖 knW? ， 一個(gè) n 階的圈 1121 , vvvvvC nnn ?? ?? ，還有 k 個(gè)頂點(diǎn)kuuu ?, 21 連接圈 nC 的每個(gè)頂點(diǎn)，且這 k 個(gè)頂點(diǎn)之間沒有邊直接相連，這樣構(gòu)成的圖就是新輪圖 knW? 。 對新輪圖 knW? 進(jìn)行染色，因?yàn)?k 個(gè)內(nèi)部頂點(diǎn) kuuu ?, 21 之間沒有直接的邊連接，為了確保內(nèi)部頂點(diǎn)之間至少有一條彩虹路連接，所以先考慮 k 個(gè)內(nèi)部頂點(diǎn)之間的彩虹路。 為了敘述簡潔，給出一個(gè) 88?W 的新輪圖，如圖 5 所示，圈 8C ，并有 8 的內(nèi)部頂點(diǎn) 821 , uuu ? 。為了便于觀看，只選取了圈 8C 上的一個(gè)頂點(diǎn) v 與內(nèi)部 8 的頂點(diǎn)相連，同時(shí)省略了 8 個(gè)內(nèi)部頂點(diǎn)與圈 8C 上別的頂點(diǎn)之間的連接邊。 可以看出， 8 個(gè)內(nèi)部頂點(diǎn)之間存在一條最短的路 ji KvK ?? ， }8,2,1{, ??ji 且ji? ，于是決定將此條路染色成彩虹路，因此邊分別染 色，色，色， 821 ??vK i ，8,2,1 ??i ，這樣的染色方法確保了 8 個(gè)內(nèi)部頂點(diǎn)之間的最短路徑 ji KvK ?? 是一條彩虹路。至于 8 個(gè)內(nèi)部頂點(diǎn)與圈 8C 上別的頂點(diǎn)之間相連邊的顏色，也完全可以從 8 種顏色中取出，且遠(yuǎn)遠(yuǎn)滿足染色需要。類似的，對于 k 個(gè)內(nèi)部頂點(diǎn)，要保證 k個(gè)內(nèi)部頂點(diǎn)中，任意兩個(gè)頂點(diǎn)之間有一條彩虹路相連，則需要的顏色數(shù)為 k 。 XVII 圖 5 88?W 的新輪圖 接下來結(jié)合圈 nC 考慮新輪圖 knW? 是彩虹連通的，可分三類情況進(jìn)行討論： 情況 1：圈 nC 上的頂點(diǎn)數(shù)與內(nèi)部頂點(diǎn) 數(shù) k 相同，即 kn? 。按照上述的染色方法，能夠保證任意兩個(gè)內(nèi)部頂點(diǎn) ik 和 jk ， ji? ，之間至少存在一條彩虹路相連，圈 上的邊的染色需要的顏色完全可以取自 k 種顏色，并且不需要取全部的 k 種顏色就能使得在圖 knW? 中，任意兩個(gè)頂點(diǎn)之間至少有一條彩虹路相連。因此，彩虹連通數(shù) kWrc kn ?? )( 。 情況 2 ：圈 nC 上的頂點(diǎn)數(shù)少于內(nèi)部頂點(diǎn)數(shù) k 相同，即 kn? 。同情況 1類似，圈 nC 上的邊的染色需要的顏色完全可以取自 k 種顏色，且遠(yuǎn)遠(yuǎn)少于 k 種，就能夠滿足在圖 knW? 中，任意兩個(gè)頂點(diǎn)之間至少有一條彩虹路相連， k 種顏色就已經(jīng)使得圖 knW? 彩虹連通。因此，彩虹連通數(shù) kWrc kn ?? )( 。 XVIII 情況 3 ：圈 nC 上的頂點(diǎn)數(shù)多余于內(nèi)部頂點(diǎn)數(shù) k ，即 kn? 。斷言這種情況下的彩虹連通數(shù)應(yīng)是 kWrc kn ?? )( ，假設(shè) kWrc kn ?? )( ，那么對于內(nèi)部的 k 個(gè)頂點(diǎn)而言，會使得其中某些頂點(diǎn)之間沒有彩虹路相連，比如說頂點(diǎn) ik 和 jk ， ji? ，},2,1{, kji ?? 之間連接的邊染了同種顏色，就沒有彩虹路。所以，假設(shè)不成立。 另一方面，要使圖 knW? 中，任意兩個(gè)頂點(diǎn)之間至少有一條彩虹路相連， k 種顏 色就已經(jīng)滿足染色需求，不需要多一種的顏色。這點(diǎn)可以從一個(gè)簡單的例子進(jìn)行說明。 為說明情況 3 ，給出一個(gè) 28?W 的新輪圖，如圖 6 所示，圈 8C ，有 2 個(gè)內(nèi)部頂點(diǎn)，所以彩虹連通數(shù) 2)( 28 ??Wrc ，就是說這個(gè)圖只需要 2 中顏色進(jìn)行染色，就可以使得圖 28?W 中任意兩個(gè)頂點(diǎn)之間至少有一條彩虹路相連，即圖 28?W 是彩虹連通的。 之前有說明 ，頂點(diǎn)數(shù) 8?n 的輪圖 8W 的彩虹連通數(shù)是 3)( 8 ?Wrc ，增加一個(gè)內(nèi)部頂點(diǎn)以后，可以使得彩虹連通數(shù)變?yōu)?2)( 28 ??Wrc 。因此，研究這類的新輪圖knW? 是有一定意義的。 XIX 圖 6 28?W 的新輪圖 對上述的討論作補(bǔ)充說明： 情況 3 中的圈 nC 上的頂點(diǎn)數(shù)多余于內(nèi)部頂點(diǎn)數(shù) k 相同，即 kn? ， n 只是相對k 而言，數(shù)量多，而不是遠(yuǎn)遠(yuǎn)大于 k 。比如說，圈 nC 中 500?n ，而內(nèi)部頂點(diǎn)數(shù) 2?k ，像這樣的 n 遠(yuǎn)遠(yuǎn)大于 k 的情況是不屬于情況 3 中所說的范圍，我們只是針對kn? ，但是兩者之間較為接近的情況進(jìn)行的一個(gè)討論。因?yàn)?n 遠(yuǎn)遠(yuǎn)大于 k 的這種情況屬于特例，某些情況下甚至找不到任何一種染色方法使得它彩虹連通，或者說它就不存在彩虹連通圖。那么這樣的圖類對于我們的研究沒有任何的意義，所以就不是情況 3 所討論的范圍。 類似的，情況 2 中圈 nC 上的頂點(diǎn)數(shù)少于內(nèi)部頂點(diǎn)數(shù) k 相同，即 kn? ，只是針對 n 和 k 相差并不是很大的情況。比方說，圈 nC 中 3?n ，而內(nèi)部頂點(diǎn)數(shù) 500?k ，按照本文的染色方法，就需要 500 種顏色才能使得圖 5003?W 彩虹連通，即500)( 5003 ??Wrc ，對于這類的圖，雖然可以計(jì)算出彩虹連通數(shù)，但是失去了圖的彩虹染色的意義，在實(shí)際的應(yīng)用中，我們對于這樣兩方相差懸殊，必定會對少的一方做一些補(bǔ)充，否則投入成本過大，這也就失去了實(shí)際應(yīng)用的意義。 綜上所述，我們可以確定新輪圖 knW? 的彩虹連通數(shù)。 當(dāng) 3?n ， 2?k 時(shí)，新輪圖 knW? 的彩虹連通數(shù)是： kWrc kn ?? )( 。 第三節(jié) 特殊圖類，廣義 ?? 圖的彩虹連通數(shù) 在討論廣義 ?? 圖之前，我們先來了解幾個(gè)定義。這些定來自參考文獻(xiàn) ]18[ 。首先是彩虹 ?k 連通，如果一條路的邊分別染不同的顏色，那么這條邊染色路就是一條彩虹路。如果圖 G 中任意兩個(gè)頂點(diǎn)之間是連通的，并且由 k 條內(nèi)部頂點(diǎn)不相交的彩虹路連通，那么邊染色圖 G 就是彩虹 ?k 連通的，其中 Nk? 。接下來，我們給出彩虹 ?k 連通數(shù) )(Grck 的定義：若存在圖 G 的一個(gè)邊染色，使用 t 種顏色就能夠使得圖 G 彩虹 ?k 連通，其中 t 是最小的整數(shù)，那么彩虹 ?k 連通數(shù)為：tGrck ?)( 。對于 ?1 連通圖的彩虹連通數(shù)，記作 )(Grc ，即 )()( 1 GrcGrc ? 。本文的概念定 義部分介紹了，一個(gè)圖 G 是 ?k 連通的，當(dāng)且僅當(dāng)任意兩個(gè)頂點(diǎn)之間是連通的，并且由 k 條內(nèi)部頂點(diǎn)不相交的路徑連通。因此，前面定義的 )(Grck 僅僅是針對 ?k 連通圖而言的。 XX 我們繼續(xù)說明 )(Grck ，在參考文獻(xiàn) ]18[ 中，對于 1?k ， Caro 等人證明了，如果圖 G 的階數(shù)為