【正文】 了證明，特別是對于路徑數(shù) 3?t 的廣義 ?? 圖，其彩虹連通數(shù) )(2 Grc 是 1?n 或者是 2?n 。 首先，了解 ?l 連通圖： 定理 .4 如果 G 是一個(gè) ?l 連通圖， 2?l ，頂點(diǎn) 1??ln ，那么 l nlGrc )1()(2 ??。那么這樣的 ?2 連通圖就是一個(gè)著名的亞族。 定理 .5 如果 G 是一個(gè) ?l 連通圖， 2?l ，頂點(diǎn) 1??ln ，那么存在圖 G 的一個(gè)邊染色，至多是 l nl )1( ? 種顏色滿足以下結(jié)論： )1( 對于任意兩個(gè)頂點(diǎn) )(, GVvu ? ，這里存在兩條不相交的彩虹 vu? 路； )2( 對于任意一個(gè)頂點(diǎn) )(GVu? ，任意集合 )(GVX? ，且 2?X ，這里兩條彩虹 Xu? 路，只有頂點(diǎn) u 相同； )3( 對于任意兩個(gè)集合 )(, GVYX ? ，且 2, ?YX ，這里的兩條彩虹 YX? 路不相交。類似的，對于)3( ，如果 X 和 Y 相交，那么一條適合的路徑是一個(gè)點(diǎn)，這點(diǎn)在 YX? 中。 定理 .6 )( 定理Fan 令 G 是一個(gè) ?k 連通圖。 定理 5 的證明：首先定義圖 G 的一些子圖 GHHH t ???? ?10 ，其中 0?t ，)()( GVHV t ? ?，F(xiàn)在，假設(shè)找到這樣一些圖 10 , ?iHH ? ， 1?i ，如果 )()( 1 GVHV i ?? ，那么集合 ti HH ??1 ，否則的話，這里存在一個(gè)頂點(diǎn))( )( 1?? ii HV GVv。令 iH 是一些 l 路 1?iH 的集合。 對于每個(gè) i ， ti??0 ，歸納證明了，存在一個(gè) iH 的邊染色，至多使用l HVl i)()1( ? 種顏色，使得定理 5 中的 )1( 到 )3( 的性質(zhì)成立，這里使用 iH 代替 G 。 接下里，先對每個(gè) iH 定義一個(gè)邊染色。假設(shè) 1?iH 有一個(gè)邊染色，顏色是 色，色， m?1 ，其中 ti??1 。假設(shè)路徑是 l ,1? ，1)()( 1 ??? lQeQe ? 。令lF ???1? ， )( 1?? ij HV? 是路勁 jQ 的另一個(gè)端點(diǎn)，其中 lj??1 。 情況 1： 12)(1 ???? lFVl ， lFVQe ?? )()( 1 ， 1)()( 2 ??? lQeQe ? 。就 1)( ??? llFV 而言，l ,2? 的染色使用顏色為 lFVmm ??? )(,1 ? ，采用這樣的染色方法，每種顏 XXII 色至少出現(xiàn)過 1次。 情況 2 ： lFV 2)( ? ， lFVQe ?? )()( 1 ， 1)()( 2 ??? lQeQe ? 。染 l ,2? 使用的所有顏色數(shù)為 1)( ??? lFVm 。 情況 3 ： 2)( 2 ?Qe 。對邊進(jìn)行染色，路徑 12?jQ 的第一條邊和路徑 jQ2 的最后一條邊染 12 ?? jm 色，路徑 12?jQ 的最后一條邊和路徑 jQ2 的第一條邊染 jm2? 色。 F 的其余的邊染不同的新的顏色。 重復(fù)歸納，可以得到 iH 的一個(gè)染色， ti??0 。顯然，對于 0H ，我們使用了 l HVlHV )()1()( 00 ??種顏色，定理 5 的 )1( 到 )3( 成立。對于情況 1和情況 3 ，因?yàn)?)( ??lFV ，所以 iH 的 總 的 使 用 顏 色 數(shù) 至 多 是l HVllFVl HVl ii )()1()()()1( 1 ????? ? 。 最后，我們在情況 1到情況 3 中驗(yàn)證，定理 5 的 )1( 到 )3( 成立對于 iH 成立。類似的，對于 )2( ， )(}{ 1?? iHVXu ? ；對于 )3( ， )(, 1?? iHVYX 。這就完成了定理 5 的 XXIII 證明，因此定理 4 也就成立了。 我們可以知道，當(dāng) G 時(shí)圈 nC ，有 n 個(gè)頂點(diǎn)時(shí)，彩虹連通數(shù) nCrc n ?)(2 。定義廣義 ?? 圖：令qtqG ,1??? ，它是 2?t 的路徑的集合，路徑的長度 11 ??? tqq ? ，其中 21??tq ，并且路勁上的每對內(nèi)部頂點(diǎn)時(shí)不相交的，而且都有兩個(gè)相同的端點(diǎn)。 圖 7 四條路徑的廣義 ?? 圖 定理 7 證明：首先定義一些子圖 GGGG t ???? ?10 ， 0?t ， 00 Q? 是一個(gè)圈。 x 和 y 一定是一些路徑j(luò)QP? 的末端點(diǎn)， ij??0 ，如果一些路徑 ),1( jlilQl ??? 的末端點(diǎn)是路徑 P 的的內(nèi)部頂點(diǎn)，那么路徑 P 一定包含了路徑 lQ 的兩個(gè)端點(diǎn)。 構(gòu)造串并聯(lián)圖，設(shè)置 )( 0GVz? ，先確定一個(gè)圈 0G ，以順時(shí)針旋轉(zhuǎn)作為參考。而 XXIV 且，假設(shè)路徑 jQ 是以 1?jG 外部為導(dǎo)向， ij??1 )2(?i 。另外，如果)( iQVz? ，對于 iQ 選擇外部和導(dǎo)向使得 z 是 iQ 的末頂點(diǎn)。加入的 iQ 和方向同上面方法一樣。因此，我們能夠重復(fù)加入和重復(fù)導(dǎo)向 11 , ?? ij ? ，按照這樣做法，對于 iG 達(dá)到一個(gè)外部和一個(gè)導(dǎo)向。 對于每個(gè) i 重復(fù)，直到 GGt? 。 接下來， iG 的邊染色， )( iGV 種顏色。假設(shè) 1?iG 是染色，使用了 )( 1?iGV 中顏色。那么 iG是染色的，使用了 )( iGV 種顏色。所以證明了定理 7 。顯然，2?t 時(shí)，圖 G 就是一個(gè)圈。 首先，因?yàn)?2)( ??? nyGe ，如果給圖 G 染色，少于 2?n 種顏色，那么對于某些頂點(diǎn)}{ )(, xyvu ??，在 yG? 中存在唯一的 vu? 路徑 P 不是彩虹路。因此，2)(2 ??nGrc 。路徑 iQ 的邊染色映射到端點(diǎn) x 和 y ，分別染色 i 和 1?i ，其中 11 ??? ti 。那么對于 G 使用了 1?n 種顏色，并且這種染色是一個(gè)彩虹 ?2 連通的，其中 3?t 。 現(xiàn)在，我們考慮對于廣義 ?? 圖進(jìn)行彩虹染色，這是在已有的基礎(chǔ)上提出更優(yōu)的彩色方法。 如圖 8 所示，廣義 ?? 圖的端點(diǎn)是 X 和 Y ，四條路徑分別是： 4321 , 。比如說，考慮路徑 1Q 和路徑 2Q 為一對，路徑 3Q 和路徑 4Q 為另一對。于是，我們可以得到，邊數(shù)總是比頂點(diǎn)數(shù)多 1，那么假設(shè) 1Q 上有 1k 個(gè)頂點(diǎn)，就有 11?k條邊，類似的， iQ 上有 ik 個(gè)頂點(diǎn)，就有 1?ik 條邊， ti??1 。此時(shí)要選取長度較長的一條進(jìn)行染色，于是選取以順時(shí)針的一條染色，分別染 色色，色，色，色， 54321 。類似的，對于路徑 13 uv? ，也取長度為 5 的路徑，未染色的邊只有 21 uu? ，并且只能染 色1 。我們都知道，一個(gè)圖是圈的話，它的彩虹連通數(shù)是 ??????? 2)( nCrc n，如果從圈的角度來驗(yàn)證，圖 YX ??? 21 的彩虹連通數(shù)是滿足的。 圖 8 四條路徑的廣義 ?? 圖 完成了路徑 1Q 和 2Q 的彩虹染色，我們再來考慮另外一對路徑 3Q 和 4Q 的彩虹染色。因?yàn)殚L度都相等，所以選取哪一條染色都不會(huì)影響結(jié)果，為了便于敘述，我們還是選取順時(shí)針的一條染色，分別染新的顏色，即色色，色，色，色， 109876 。類似的，對于路徑 23 uv? ，也選取順時(shí)針的一條，長度是 5 ，只有邊 32 uu? 未染色，并且只能染 色6 。這樣的染色后，只剩下邊 1vX? 和邊 1uX? 未被染色，可以分別取 色8 和 色9 ，就能確保在圖 YX ??? 43 中，任意兩個(gè)頂點(diǎn)之間至少有一條彩虹路，那么彩虹連通數(shù) 5)( 43 ???? YXrc 。 圖 9 四條路徑的廣義 ?? 圖 到這一步，我們就完成了這個(gè)只有四條路徑 4321 , 的廣義 ?? 圖的彩虹染色，運(yùn)用這樣的彩色方法，就使得圖中任意兩個(gè)頂點(diǎn)之間至少有一條彩虹路相連，廣義 ?? 圖是彩虹連通的，并且彩虹連通數(shù)是 10)( ??rc 。而按照本文的染色方法得到的彩虹連通數(shù)是 10)( ??rc ，少于計(jì)算出的彩虹連通數(shù)，所以本文的給出的針對廣義 ?? 圖的染色方法可以減少所使用的顏色數(shù)，是有意義的染色方法。按照本文的染色方法，我們分路徑數(shù) t 是偶數(shù)和奇數(shù)的情況討 論： 情況 1： 3?t ，且 t 是偶數(shù)。 如果路徑 t ,1 ? 的頂點(diǎn)數(shù)分別是： tkk ,1? ，且 nkk t ????1 ，那么彩虹連通數(shù) ?????? ?????????? ???? ? 1212)( 121 tt kkkkrc ?， nkk t ????1 。這類廣義 ?? 圖從最里的一對路徑 1Q 和 2Q 開始染色，直到最外的一對路徑 2?tQ 和 1?tQ ，這些染色方式按照本文介紹的方法進(jìn)行染色。要使 tQ 是一條彩虹路，則這條路上的邊必須染不同的顏色，有 tk 個(gè)頂點(diǎn)，則需要 1?tk 種顏色。 無論是情況 1還是情況 2 ，按照本文方法進(jìn)行的彩虹染色，得到的彩虹連通數(shù) )(?rc 都優(yōu)于 )(2 Grc 。3,322。 XXIX 第三章 結(jié)語 本文是課題是“特殊圖類的彩虹邊染色”，選取三類特殊圖。利用改善后的 ?3 連通圖的彩虹連通數(shù) 5 )1(3)( ?? nGrc 說明了 )( xGrc 是有意義的。并且說明了，當(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。 本文選取這三類特殊圖進(jìn)行彩虹染色，也得到了相應(yīng)的彩虹連通數(shù) )(Grc ，或許本文的染色方法并不是最優(yōu)異的，得到的彩虹連通數(shù) )(Grc 也不是最小的，這點(diǎn)是由于知識(shí)水平的有限，不能做到最優(yōu)秀，還望閱讀過本文的讀者給予意見，我會(huì)進(jìn)一步改善染色方法，得到更優(yōu)的彩虹連通數(shù)。 [8]， to Graph Theory. Boston， 2020； [9]， . The Probabilistic Method. New York， 2020。 [11]Chandran L， Das A， Rajendraprasad D， et connection number and connected dominating sets. J Graph Theory， 2020， 71： 206218。 [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