【正文】 [12]Xueliang Li, Yongtang connection in 3connected Graphs。 [10],et al. On rainbow connection. Electron J Combin 15, R57 (2020)。 XXX 參考文獻 [1]宋慧敏 吳建良 . Halin圖的均勻邊染色 [J]. 山東大學(xué)學(xué)報， 2020 38:3134； [2]董九英，李學(xué)良 .圖的彩虹連通數(shù)與最小度和 [J].中國科學(xué)：數(shù)學(xué)， 2020,43:714； [5]萬慧敏，史小藝，王艷麗 .幾種特殊圖的邊染色 [J].五邑大學(xué)學(xué)報， 2020 26:78； [6]苗蓮英 .圖的邊覆蓋染色 [D].山東大學(xué)博士論文， 2020 25:2124； [7],et al. Rainbow connection in graphs. Math Bohem， 2020。第三類是： n 個頂點的廣義 ?? 圖，按照本文的染色方法進行彩虹染色，使得廣義 ?? 圖是彩虹連通的，并計算出了這類圖的彩虹連通數(shù) )(?rc ，而現(xiàn)有的廣義 ?? 圖的彩虹連通數(shù)是 21)(2 ??? nnGrc 或 ，其中路徑數(shù) 3?t ，本文染色得出的 )(?rc 遠(yuǎn)比現(xiàn)有的 )(2 Grc 優(yōu)異許多。第二類是：圈為 nC ，有 k 個內(nèi)部頂點的新輪圖 knW? ，按照本文的染色方法進行彩虹染色，使得圖 knW? 是彩虹連通的，并計算出了這類圖的彩虹連通數(shù)，kWrc kn ?? )( ，其中圈上頂點數(shù) 3?n ，內(nèi)部的頂點數(shù) 2?k 。第一類是：度為 3 的 Halin 圖 xG ，按照本文的染色方法進行彩虹染色，使得圖 xH 是彩虹連通的，并計算出了這類圖的彩虹連通數(shù)， 423)( 2 ??? ?kkGrc ，其中 k 是層數(shù)，且3?k 。22)(21是奇數(shù)且是偶數(shù)且，tttjiktkktttjitkktkkrctjiji 其中， n 個頂點是指不計算端點 X 和 Y ，只是 t 條路徑上頂點的總數(shù)，即ji kkn ?? ， tji ???2 。綜上所述， n 個頂點的廣義 ?? 圖的彩虹連通數(shù)是： ???????????????????????? ???????????? ???????? ???.3,3,212。所以，這類的廣義 ?? 圖的彩虹連通數(shù) 11212)( 1221 ???????? ?????????? ???? ?? ttt kkkkkrc ?，nkk t ????1 。這里的問題只是在于還有一條單一 的路徑 tQ ，我們只需要使得這條路徑是一條彩虹路，就能夠保證整個廣義 ?? 圖彩虹連通。 情況 2 ： 3?t ，且 t 是奇數(shù)。這類廣義 ?? 圖從最里的一對路徑 1Q 和 2Q 開始染色，直到最外的一對路徑 1?tQ 和 tQ 。 接下來，我們考慮頂點數(shù)是 n（不計算端點 X 和 Y ），路徑數(shù) 3?t 的廣義 ?? XXVIII 圖。在前面，我們給出了有 n 個頂點，路徑數(shù) 3?t 的廣義 ?? 圖的彩虹連通數(shù) 1)(2 ??nGrc 或者2)(2 ??nGrc ，按照這樣的計算，本文的四條路徑的廣義 ?? 圖，頂點數(shù) 15?n （不計算端點 X 和 Y ），那么彩虹連通 數(shù)至少也是 13)(2 ?Grc 。按照上面的推廣，如果 3Q 的頂點數(shù)變?yōu)?3k ， 4Q 的頂點數(shù)變?yōu)?4k ，那么對于圖 YX ??? 43 還是采用上述的方法進行彩虹染色，于是彩虹連通數(shù)是： ?????? ?????? 12)( 4343 kkYXrc。再選取 XXVII 路徑 14 uv? ，選取順時針的一條，長度是 5 ，只有邊 21 uu? 未染色，并且只能染 色7 。剩下邊的染色，顏色一定取自這五種顏色，所以我們可以這樣考慮，路徑 41 uv? ，也可以分為順時針的一條，長度是 5 ，和逆時針的一條，長度也是 5 ，還是對順時針的一條進行染色，發(fā)現(xiàn)只有邊 21 vv? 沒有染色，并且五種顏色中只可以選取 色10 ，所以染 色10 。采取相同的染色方法，考慮圖 YX ??? 43 ，如圖 9 所示，圖上總的有 10條邊，考慮最遠(yuǎn)的兩個頂點（端點 X 和 Y 不作為首先考慮的頂點）， 2v 和 3u ，形成了兩條 32 uv? 路，順時針的一條，即 34432 , uuvvv ，長度為 5 ，逆時針的一條，即 32112 , uuuvv ，長度也為 5 ?；氐綀D YX ??? 21 的推廣上，上面的例子中的路徑 1Q 和 2Q 上的 XXVI 頂點數(shù)是具體的，如果 1Q 的頂點數(shù)變?yōu)?1k ， 2Q 的頂點數(shù)變?yōu)?2k ，那么對于圖YX ??? 21 還是采用上述的方法進行彩虹染色，于是彩虹連通數(shù)是：?????? ?????? 12)( 2121 kkYXrc 。這樣的染色后，只剩下邊 1vX? 和邊 1uX? 未被染色，可以分別取 色2和 色3 ，就能確保在 YX ??? 21 中，任意兩個頂點之間至少有一條彩虹路，那么彩虹連通數(shù) 5)( 21 ???? YXrc 。剩下邊的染色，顏色一定取自這五種顏色，我們這么考慮，路徑 31 uv? ，也可以分為順時針的一條，和逆時針的一條，可以看到的是順時針的一條長度是 5 ，所以考慮這條路徑的染色，發(fā)現(xiàn)邊 21 vv? 沒有染色，并且 5 中顏色中只剩下 色5 ，所以染 色5 。 回到路徑 1Q 和路徑 2Q 的染色上，顯然這兩條路徑加上端點 X 和 Y 就是一個圈，總的有 9 條邊 ，考慮最遠(yuǎn)的兩個頂點（端點 X 和 Y 不作為首先考慮的頂點），2v 和 2u ，這樣就形成了兩條 22 uv? 路，順時針的一條，即 23432 , uuuvv ，長度為5 ，逆時針的一條，即 2112 , uuvv ，長度為 4 。路徑 1Q 上有 3個頂點， 321 , vvv ，有 4 條邊；路徑 2Q 上有 4 個頂點， 4321 , uuuu ，有 5 條邊。我們的染色方法是從里面的路徑開始，以相對的兩條路徑為一對來進行染色。以簡單的只有 4 條路徑的廣義 ?? 圖來說明染色方法，然后推理到有 t 條路徑的廣義 ?? 圖。因此， 1)(2 ??nGrc 。下一步，對別的邊染不同的顏色。 XXV 接下來，對 G 染色。但是在 G中，有唯一的一對不相交的 vu? 路，并且 P 是其中的一條路徑。因此，假設(shè) 3?t 。 完成了 ?2 連通串并聯(lián)圖 G ，最后考慮廣義 ?? 圖， 參考了文獻 ]18[ ： 定理 .8 如果 qtqG ,1??? 是一個廣義 ?? 圖，頂點數(shù) 為 n ，那么 ??? ????? 3,21 2,)(2 tnntnGrc 或 定理 8 證明：假設(shè) t ,1? 是 t 條路徑， yx, 是 t 條路徑的共同的端點。因此，證明了，對于每個 i ， iH 是彩虹連通的。 iQ 加入到 1?iG 的外部。首先， 0G 是彩虹染色，使用了 )( 0GV中顏色。假設(shè) iH 是 iG 的外部圈， ti??0 ，使得)( iHVz? 。最后，重復(fù)標(biāo)簽 11 , ?? ijj Q ? 分別是 ijj Q , 21 ??? 。注意點， iQ 是加入到由 1?jQ 造出的外部界，當(dāng) iQ 加入 jG 的外部。 否則，刪除 ?, 21 ?? ii 直到第一個 )10( ??? ijj 使得加入的 iQ 在 jG 的外部。如果增加的路徑 jQ 是以1?jG 外部為導(dǎo)向，那么 iQ 導(dǎo)向使得， z 任然在 iG 新的外部圈中。對于 jG 定義一個方向和一個平面，以 jG 的外部為導(dǎo)向順時針圈，且包 含 z 。每個 )0( tiGi ?? 是一個 ?2 連通串并聯(lián)圖。 iG 是從 1?iG 附加一條長度至少為 1的路徑 iQ 到 1?iG 得到的， ti??1 ，用兩個不同的頂點 )(, 1?? iGVyx 來辨別路徑 iQ 的末端點。如圖 7 所示的就是一個有四條路徑的廣義 ?? 圖。這是特殊情況，更為一般的情況是，圖 G 是一個廣義 ?? 圖。 完成了 ?l 連通圖 G 的介紹，接下來考慮圖 G 是一個 ?2 連通的串并聯(lián)圖， 參考文獻 ]18[ ： 定理 .7 如果圖 G 是一個 ?2 連通的串并聯(lián)圖，頂點 3?n ，那么 nGrc ?)(2 。現(xiàn)在，對于 iH 證明了 )1( 到 )3( 成立。對于 )1( 歸納假設(shè)，如果 )(, 1?? iHVvu 。對于情況 2 ，因為 FV 2)( ? ，所以 iH 的總的使用顏色數(shù)至多是： l HVllFVl HVl ii )()1(1)()()1( 1 ?????? ? 。現(xiàn)在，假設(shè)對于 1?iH 的染色，至多使用了l HVl i )()1( 1?? 種顏色，定理 5 的 )1( 到 )3( 成立。歸納證明了，對于 iH 的染色滿足所有的需求， ti??0 ?？偟氖褂昧?lFV ?)( 種新的顏色。路徑 12?sQ 的最后一條邊和路徑ls ,22 ?? （每一條長度為 1）染 12 ?? sm 色。 假設(shè)存在最大的整數(shù) s ， ls 211 ?? ，使得 2)(,),( 21 ?sQeQe ? ?？偟?，使用了 1)( ??lFV 種新顏色。 彩虹染色 1Q 使用的顏色為 lFVmm ??? )(,1 ? 。總的，使用了 lFV ?)( 種新的顏色。 彩虹染色 1Q 使用的顏色為 lFVmm ??? )(,1 ? 。分別把 jQ的第一條邊和最后一條邊射入到 iv 和 j? 。對于 2?l 的 情 況 ， 可 以 假 設(shè) 1)()( 21 ?? QeQe 。通過附加一個細(xì)分的 lK,1 到 1?iH 得到圖 iH ，其中 l 條路徑匯集于頂點 iv 。顯然， 0H 是一個圈，它是彩虹染色的。那么，集合 ti? 就意味著對于 G 而言定理 4 成立。重復(fù)這個過程，直到結(jié)束。根據(jù)定 理 6 ， iv 發(fā)出 l 路到 1?iH ，這里的每對路徑僅僅匯集與 iv ，那些 l 路是 lK,1 的一個細(xì)分。因為任意的 ?l 連通圖都含有一個頂點至少是 l 的圈，于是令 0H 是圖 G 的一個頂點至少是 l 的圈。對于任意的頂點 )(GVu? 和任意集合 )( uGVX ?? ， kX? ，這里有從 u 到 X 的 k 條路徑，使得對于其中的任意兩條路，僅僅只有一個共同頂點 u 。 XXI 顯然，定理 1是來自定理 4 ，所以先證明定理 4 ，證明之前先給出一個定理 5 。 對于 )2( 而言，如果 Xu? ，那么其中的一條路徑取自頂點 u 。 證明定理 4 ，我們是通過先證明一個強有力的定理 5 的 結(jié)論，然后間接證明定理 4 。 在情況 2?l 中，如果圖 G 是一個 ?2 連通串并聯(lián)圖是一個簡單圖，從 三個頂點 3K 開始，反復(fù)運用一個操作序列，這個序列是一個分支，由一條邊變換成雙條邊，反復(fù)增加分支邊。本文會提供一種新的染色方法，使得廣義 ?? 圖是彩虹連通的，并且彩虹連通數(shù) )(Grc 小于2?n 。另外，上文有說明圖G 是 ?3 連通的，即 3?k ，可以采用改善后的界，即 5 )1(3)( ?? nGrc 。 Chandran 等人證明了，如果圖 G 的最小度為 ? ，那么313)( ???? nGrc ，并且證明了對于所有階數(shù)為 n ，最小度為 ? 的連通圖 G 都是適用的。因此，前面定義的 )(Grck 僅僅是針對 ?k 連通圖而言的。對于 ?1 連通圖的彩虹連通數(shù)，記作 )(Grc ，即 )()( 1 GrcGrc ? 。如果圖 G 中任意兩個頂點之間是連通的，并且由 k 條內(nèi)部頂點不相交的彩虹路連通，那么邊染色圖 G 就是彩虹 ?k 連通的，其中 Nk? 。這些定來自參考文獻 ]18[ 。 當(dāng) 3?n ， 2?k 時，新輪圖 knW? 的彩虹連通數(shù)是： kWrc kn ?? )(