【正文】 個(gè)（ nC 與相連的結(jié)點(diǎn)構(gòu)成的七個(gè)頂點(diǎn)）的子圖。 進(jìn)一步說(shuō)明此種染色方法得到的 Halin 圖是彩虹連通的。 因?yàn)橐粋€(gè)子圖中任意一個(gè)頂點(diǎn)有三條邊連接，所以這樣的兩個(gè)頂點(diǎn)之間有許多條路連接，只要確保這條路徑在子圖 iH 和 jH 中邊的顏色不同，那么這條路一定是彩虹路，也就是說(shuō)任意兩點(diǎn)之間至少有一條彩虹路連接。因此，本文需要再次聲明，采取的染色方法是較為保守的，但是確保了這種的染色方法，一定使得圖 kG 中任意兩個(gè)頂點(diǎn)之間至少有一條彩虹路相連，是滿(mǎn)足了讓圖 kG 彩虹連通。 并且這個(gè)上界是針對(duì)所有的 ?3 連通圖而言的，而本文驗(yàn)證的是一個(gè)特殊的 ?3 連通圖，它的所有頂點(diǎn)的度為 3 ，即 3?? ， 343)( ?? nGrc 。而 rSchiermeye 證明了，對(duì)于最小度為 3 的圖 G ，即 3?? ，那么它的彩虹連通數(shù)為 43)( nGrc ? 。從 Chandran 等人的結(jié)論中，我們能夠容易推出彩虹連通數(shù)的一個(gè)上界： 31)( 3313)( ?????? Gk nnGrc ? 因此，對(duì)于連通度 3)( ?Gk ，彩虹連通數(shù) 343)( ?? nGrc ，連通度 4)( ?Gk ，彩虹連通數(shù) 353)( ?? nGrc 。 如果，圖 G 中含有一個(gè)三角形 3C ，令 3CH? ，那么 581)(3 ??Crc。令邊 ijf 映射到頂點(diǎn) ix ， 3,2,1?j 。 515 )4(3251532)()( ????????? hhHrcHrc 這就說(shuō)明了至少其中有四個(gè)頂點(diǎn)，例如 x ，有這樣的屬性，其中的三條內(nèi)部不相交 ?),( Hx 路徑 210 , PPP 的長(zhǎng)度至少是 2 。進(jìn)一步，先假設(shè) 3??ts 。我們對(duì)邊 0e 的染色可以選擇 H 中已經(jīng)重復(fù)的 任意一種顏色，那么這就簡(jiǎn)單驗(yàn)證了 H? 是彩虹連通的。這就證明了H? 是彩虹連通的。 如果 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 就關(guān)于層數(shù) k 的函數(shù)，423)( 2 ??? ?kkGrc ，而 )(Grc 也可變換為有關(guān)層數(shù) k 的函數(shù)， 5 329)( ??? xGrc 。對(duì)于 3?n 的圈，在圈中加入一個(gè)頂點(diǎn) 1K ，使得 1K 與圈上的每個(gè)頂點(diǎn)連接，那么這樣的圖 1KCn? 就稱(chēng)作輪圖 nW 。 新輪圖 knW? 是一個(gè)有 k 個(gè)內(nèi)部頂點(diǎn) kvvv , 21 ? ，但 k 個(gè)頂點(diǎn)之間沒(méi)有邊直接 XV 相連接，有 n 個(gè)葉子頂點(diǎn)，且被一個(gè)圈連接的圖，根據(jù) Halin 圖的定義，可知新輪圖 knW? 并不是一個(gè)特殊的 Halin 圖，但是它的特殊性值得研究，那么新輪圖knW? 的最小度 },2m in{ nk ??? 。這時(shí)的輪圖是一個(gè)完全圖，因此 1)( 3 ?Wrc 。 最后考慮，當(dāng) 7?n 時(shí)。因?yàn)?7?n 的 nW 不是一個(gè)完全圖，于是2)( ?nWrc 。這就使得 2)( 3 ?vvc ，反過(guò)來(lái)使得 1)( 1 ??vvc n 。因此綜上， 3)( ?nWrc 。為了便于觀看，只選取了圈 8C 上的一個(gè)頂點(diǎn) v 與內(nèi)部 8 的頂點(diǎn)相連，同時(shí)省略了 8 個(gè)內(nèi)部頂點(diǎn)與圈 8C 上別的頂點(diǎn)之間的連接邊。 XVII 圖 5 88?W 的新輪圖 接下來(lái)結(jié)合圈 nC 考慮新輪圖 knW? 是彩虹連通的，可分三類(lèi)情況進(jìn)行討論： 情況 1：圈 nC 上的頂點(diǎn)數(shù)與內(nèi)部頂點(diǎn) 數(shù) k 相同，即 kn? 。同情況 1類(lèi)似，圈 nC 上的邊的染色需要的顏色完全可以取自 k 種顏色，且遠(yuǎn)遠(yuǎn)少于 k 種，就能夠滿(mǎn)足在圖 knW? 中，任意兩個(gè)頂點(diǎn)之間至少有一條彩虹路相連， k 種顏色就已經(jīng)使得圖 knW? 彩虹連通。所以，假設(shè)不成立。 之前有說(shuō)明 ，頂點(diǎn)數(shù) 8?n 的輪圖 8W 的彩虹連通數(shù)是 3)( 8 ?Wrc ，增加一個(gè)內(nèi)部頂點(diǎn)以后，可以使得彩虹連通數(shù)變?yōu)?2)( 28 ??Wrc 。因?yàn)?n 遠(yuǎn)遠(yuǎn)大于 k 的這種情況屬于特例，某些情況下甚至找不到任何一種染色方法使得它彩虹連通，或者說(shuō)它就不存在彩虹連通圖。 綜上所述，我們可以確定新輪圖 knW? 的彩虹連通數(shù)。首先是彩虹 ?k 連通，如果一條路的邊分別染不同的顏色，那么這條邊染色路就是一條彩虹路。本文的概念定 義部分介紹了，一個(gè)圖 G 是 ?k 連通的，當(dāng)且僅當(dāng)任意兩個(gè)頂點(diǎn)之間是連通的，并且由 k 條內(nèi)部頂點(diǎn)不相交的路徑連通。因此，如果圖 G 是 ?l 連通的，那么 313)( ??? l nGrc 。 首先，了解 ?l 連通圖： 定理 .4 如果 G 是一個(gè) ?l 連通圖， 2?l ，頂點(diǎn) 1??ln ，那么 l nlGrc )1()(2 ??。 定理 .5 如果 G 是一個(gè) ?l 連通圖， 2?l ，頂點(diǎn) 1??ln ，那么存在圖 G 的一個(gè)邊染色，至多是 l nl )1( ? 種顏色滿(mǎn)足以下結(jié)論： )1( 對(duì)于任意兩個(gè)頂點(diǎn) )(, GVvu ? ，這里存在兩條不相交的彩虹 vu? 路； )2( 對(duì)于任意一個(gè)頂點(diǎn) )(GVu? ，任意集合 )(GVX? ，且 2?X ，這里兩條彩虹 Xu? 路，只有頂點(diǎn) u 相同； )3( 對(duì)于任意兩個(gè)集合 )(, GVYX ? ，且 2, ?YX ，這里的兩條彩虹 YX? 路不相交。 定理 .6 )( 定理Fan 令 G 是一個(gè) ?k 連通圖?，F(xiàn)在，假設(shè)找到這樣一些圖 10 , ?iHH ? ， 1?i ，如果 )()( 1 GVHV i ?? ，那么集合 ti HH ??1 ，否則的話(huà)，這里存在一個(gè)頂點(diǎn))( )( 1?? ii HV GVv。 對(duì)于每個(gè) i ， ti??0 ，歸納證明了，存在一個(gè) iH 的邊染色，至多使用l HVl i)()1( ? 種顏色，使得定理 5 中的 )1( 到 )3( 的性質(zhì)成立，這里使用 iH 代替 G 。假設(shè) 1?iH 有一個(gè)邊染色，顏色是 色，色， m?1 ，其中 ti??1 。令lF ???1? ， )( 1?? ij HV? 是路勁 jQ 的另一個(gè)端點(diǎn)，其中 lj??1 。就 1)( ??? llFV 而言，l ,2? 的染色使用顏色為 lFVmm ??? )(,1 ? ，采用這樣的染色方法，每種顏 XXII 色至少出現(xiàn)過(guò) 1次。染 l ,2? 使用的所有顏色數(shù)為 1)( ??? lFVm 。對(duì)邊進(jìn)行染色，路徑 12?jQ 的第一條邊和路徑 jQ2 的最后一條邊染 12 ?? jm 色，路徑 12?jQ 的最后一條邊和路徑 jQ2 的第一條邊染 jm2? 色。 重復(fù)歸納，可以得到 iH 的一個(gè)染色， ti??0 。對(duì)于情況 1和情況 3 ，因?yàn)?)( ??lFV ，所以 iH 的 總 的 使 用 顏 色 數(shù) 至 多 是l HVllFVl HVl ii )()1()()()1( 1 ????? ? 。類(lèi)似的，對(duì)于 )2( ， )(}{ 1?? iHVXu ? ；對(duì)于 )3( ， )(, 1?? iHVYX 。 我們可以知道，當(dāng) G 時(shí)圈 nC ，有 n 個(gè)頂點(diǎn)時(shí)，彩虹連通數(shù) nCrc n ?)(2 。 圖 7 四條路徑的廣義 ?? 圖 定理 7 證明：首先定義一些子圖 GGGG t ???? ?10 ， 0?t ， 00 Q? 是一個(gè)圈。 構(gòu)造串并聯(lián)圖，設(shè)置 )( 0GVz? ，先確定一個(gè)圈 0G ，以順時(shí)針旋轉(zhuǎn)作為參考。另外，如果)( iQVz? ，對(duì)于 iQ 選擇外部和導(dǎo)向使得 z 是 iQ 的末頂點(diǎn)。因此，我們能夠重復(fù)加入和重復(fù)導(dǎo)向 11 , ?? ij ? ，按照這樣做法，對(duì)于 iG 達(dá)到一個(gè)外部和一個(gè)導(dǎo)向。 接下來(lái)， iG 的邊染色， )( iGV 種顏色。那么 iG是染色的，使用了 )( iGV 種顏色。顯然，2?t 時(shí)，圖 G 就是一個(gè)圈。因此，2)(2 ??nGrc 。那么對(duì)于 G 使用了 1?n 種顏色，并且這種染色是一個(gè)彩虹 ?2 連通的，其中 3?t 。 如圖 8 所示，廣義 ?? 圖的端點(diǎn)是 X 和 Y ，四條路徑分別是： 4321 , 。于是，我們可以得到，邊數(shù)總是比頂點(diǎn)數(shù)多 1，那么假設(shè) 1Q 上有 1k 個(gè)頂點(diǎn)，就有 11?k條邊，類(lèi)似的， iQ 上有 ik 個(gè)頂點(diǎn)，就有 1?ik 條邊， ti??1 。類(lèi)似的，對(duì)于路徑 13 uv? ，也取長(zhǎng)度為 5 的路徑，未染色的邊只有 21 uu? ，并且只能染 色1 。 圖 8 四條路徑的廣義 ?? 圖 完成了路徑 1Q 和 2Q 的彩虹染色，我們?cè)賮?lái)考慮另外一對(duì)路徑 3Q 和 4Q 的彩虹染色。類(lèi)似的，對(duì)于路徑 23 uv? ，也選取順時(shí)針的一條，長(zhǎng)度是 5 ，只有邊 32 uu? 未染色，并且只能染 色6 。 圖 9 四條路徑的廣義 ?? 圖 到這一步，我們就完成了這個(gè)只有四條路徑 4321 , 的廣義 ?? 圖的彩虹染色，運(yùn)用這樣的彩色方法，就使得圖中任意兩個(gè)頂點(diǎn)之間至少有一條彩虹路相連，廣義 ?? 圖是彩虹連通的，并且彩虹連通數(shù)是 10)( ??rc 。按照本文的染色方法，我們分路徑數(shù) t 是偶數(shù)和奇數(shù)的情況討 論： 情況 1： 3?t ，且 t 是偶數(shù)。這類(lèi)廣義 ?? 圖從最里的一對(duì)路徑 1Q 和 2Q 開(kāi)始染色，直到最外的一對(duì)路徑 2?tQ 和 1?tQ ，這些染色方式按照本文介紹的方法進(jìn)行染色。 無(wú)論是情況 1還是情況 2 ，按照本文方法進(jìn)行的彩虹染色，得到的彩虹連通數(shù) )(?rc 都優(yōu)于 )(2 Grc 。 XXIX 第三章 結(jié)語(yǔ) 本文是課題是“特殊圖類(lèi)的彩虹邊染色”，選取三類(lèi)特殊圖。并且說(shuō)明了，當(dāng) 8?n時(shí)，輪圖 8W 的彩虹連通數(shù)是 3)( 8 ?Wrc ，而增加一個(gè)內(nèi)部頂點(diǎn)，變成新輪圖 28?W ，雖然邊數(shù)增加 8 ，但是彩虹連通數(shù)卻是 2)( 28 ??Wrc ，比輪圖 8W 減少了 1。 [8]， to Graph Theory. Boston， 2020； [9]， . The Probabilistic Method. New York， 2020。 [13]Bondy, . and Murty, .: Graph Theory, GTM 244, Springer (2020) [14]Chakraborty, S., Fischer, E., Matsliah, A., Yuster, R.: Hardness and algorithms for rainbow connectivity, J. Comb. Optim. (in press) [15]Krivelevich, M., Yuster, R.: The rainbow connection of a graph is (at most) reciprocal to its minimum degree, J. Graph Theory 63(3), 185–191 (2020) [16]Li, X., and Sun, Y., Rainbow Connections of Graphs, Springer Briefs in Math., Springer, New York, 2020. [17]Schiermeyer, I.: Rainbow connection in graphs with minimum degree three, IWOCA 2020, LNCS 5874, 432–437 (2020) [18]Shinya Fujita, Henry Liuy, Colton kConnection in Dense Graphs [20]Xueliang Li, Sujuan connection number and the number of blocks