【導讀】我們都知道，圖論是源于一個著名的問題——哥尼斯堡七橋問題。論上有著重要的意義而且在實際問題中也有著重要的應用。事等眾多領域一直以來都有許多專家學者所研究。我們得介紹下何謂染色。所謂的染色問題，就是給定一個圖，需要把圖中的所有。優(yōu)秀的染色方法，就是盡量使得需要的顏色數(shù)最少。果，并且這些結果仍在進一步完善中。概念，這是對經(jīng)典連通性概念的一種加強。事實上，政府機構之間需要進行一些機密信息的傳遞，這些傳輸要保證其安。全性，于是便產(chǎn)生了彩虹連通的這些概念。假設信息的傳輸是在一個蜂窩形狀的。每一段路需要分配一個獨特的頻道。且默認V和E的交集為空集。圖的分類眾多，本文所研究的圖均為有限的簡單無向圖。指頂點的個數(shù)稱，記作G。行邊的條數(shù)稱為重數(shù)。，稱P是一條0x和kx之間的路。中的最大值，稱為是圖G的直徑，記作)(Gdiam。為了說明上述的)1(，我們考慮Petersen圖P。由于圖P中任意兩個不相鄰頂點之間有且僅有

　　

【正文】 上有 4 個頂點， 4321 , uuuu ，有 5 條邊。于是，我們可以得到，邊數(shù)總是比頂點數(shù)多 1，那么假設 1Q 上有 1k 個頂點，就有 11?k條邊，類似的， iQ 上有 ik 個頂點，就有 1?ik 條邊， ti??1 。 回到路徑 1Q 和路徑 2Q 的染色上，顯然這兩條路徑加上端點 X 和 Y 就是一個圈，總的有 9 條邊 ，考慮最遠的兩個頂點（端點 X 和 Y 不作為首先考慮的頂點），2v 和 2u ，這樣就形成了兩條 22 uv? 路，順時針的一條，即 23432 , uuuvv ，長度為5 ，逆時針的一條，即 2112 , uuvv ，長度為 4 。此時要選取長度較長的一條進行染色，于是選取以順時針的一條染色，分別染 色色，色，色，色， 54321 。剩下邊的染色，顏色一定取自這五種顏色，我們這么考慮，路徑 31 uv? ，也可以分為順時針的一條，和逆時針的一條，可以看到的是順時針的一條長度是 5 ，所以考慮這條路徑的染色，發(fā)現(xiàn)邊 21 vv? 沒有染色，并且 5 中顏色中只剩下 色5 ，所以染 色5 。類似的，對于路徑 13 uv? ，也取長度為 5 的路徑，未染色的邊只有 21 uu? ，并且只能染 色1 。這樣的染色后，只剩下邊 1vX? 和邊 1uX? 未被染色，可以分別取 色2和 色3 ，就能確保在 YX ??? 21 中，任意兩個頂點之間至少有一條彩虹路，那么彩虹連通數(shù) 5)( 21 ???? YXrc 。我們都知道，一個圖是圈的話，它的彩虹連通數(shù)是 ??????? 2)( nCrc n，如果從圈的角度來驗證，圖 YX ??? 21 的彩虹連通數(shù)是滿足的?；氐綀D YX ??? 21 的推廣上，上面的例子中的路徑 1Q 和 2Q 上的 XXVI 頂點數(shù)是具體的，如果 1Q 的頂點數(shù)變?yōu)?1k ， 2Q 的頂點數(shù)變?yōu)?2k ，那么對于圖YX ??? 21 還是采用上述的方法進行彩虹染色，于是彩虹連通數(shù)是：?????? ?????? 12)( 2121 kkYXrc 。 圖 8 四條路徑的廣義 ?? 圖 完成了路徑 1Q 和 2Q 的彩虹染色，我們再來考慮另外一對路徑 3Q 和 4Q 的彩虹染色。采取相同的染色方法，考慮圖 YX ??? 43 ，如圖 9 所示，圖上總的有 10條邊，考慮最遠的兩個頂點（端點 X 和 Y 不作為首先考慮的頂點）， 2v 和 3u ，形成了兩條 32 uv? 路，順時針的一條，即 34432 , uuvvv ，長度為 5 ，逆時針的一條，即 32112 , uuuvv ，長度也為 5 。因為長度都相等，所以選取哪一條染色都不會影響結果，為了便于敘述，我們還是選取順時針的一條染色，分別染新的顏色，即色色，色，色，色， 109876 。剩下邊的染色，顏色一定取自這五種顏色，所以我們可以這樣考慮，路徑 41 uv? ，也可以分為順時針的一條，長度是 5 ，和逆時針的一條，長度也是 5 ，還是對順時針的一條進行染色，發(fā)現(xiàn)只有邊 21 vv? 沒有染色，并且五種顏色中只可以選取 色10 ，所以染 色10 。類似的，對于路徑 23 uv? ，也選取順時針的一條，長度是 5 ，只有邊 32 uu? 未染色，并且只能染 色6 。再選取 XXVII 路徑 14 uv? ，選取順時針的一條，長度是 5 ，只有邊 21 uu? 未染色，并且只能染 色7 。這樣的染色后，只剩下邊 1vX? 和邊 1uX? 未被染色，可以分別取 色8 和 色9 ，就能確保在圖 YX ??? 43 中，任意兩個頂點之間至少有一條彩虹路，那么彩虹連通數(shù) 5)( 43 ???? YXrc 。按照上面的推廣，如果 3Q 的頂點數(shù)變?yōu)?3k ， 4Q 的頂點數(shù)變?yōu)?4k ，那么對于圖 YX ??? 43 還是采用上述的方法進行彩虹染色，于是彩虹連通數(shù)是： ?????? ?????? 12)( 4343 kkYXrc。 圖 9 四條路徑的廣義 ?? 圖 到這一步，我們就完成了這個只有四條路徑 4321 , 的廣義 ?? 圖的彩虹染色，運用這樣的彩色方法，就使得圖中任意兩個頂點之間至少有一條彩虹路相連，廣義 ?? 圖是彩虹連通的，并且彩虹連通數(shù)是 10)( ??rc 。在前面，我們給出了有 n 個頂點，路徑數(shù) 3?t 的廣義 ?? 圖的彩虹連通數(shù) 1)(2 ??nGrc 或者2)(2 ??nGrc ，按照這樣的計算，本文的四條路徑的廣義 ?? 圖，頂點數(shù) 15?n （不計算端點 X 和 Y ），那么彩虹連通 數(shù)至少也是 13)(2 ?Grc 。而按照本文的染色方法得到的彩虹連通數(shù)是 10)( ??rc ，少于計算出的彩虹連通數(shù)，所以本文的給出的針對廣義 ?? 圖的染色方法可以減少所使用的顏色數(shù)，是有意義的染色方法。 接下來，我們考慮頂點數(shù)是 n（不計算端點 X 和 Y ），路徑數(shù) 3?t 的廣義 ?? XXVIII 圖。按照本文的染色方法，我們分路徑數(shù) t 是偶數(shù)和奇數(shù)的情況討 論： 情況 1： 3?t ，且 t 是偶數(shù)。這類廣義 ?? 圖從最里的一對路徑 1Q 和 2Q 開始染色，直到最外的一對路徑 1?tQ 和 tQ 。 如果路徑 t ,1 ? 的頂點數(shù)分別是： tkk ,1? ，且 nkk t ????1 ，那么彩虹連通數(shù) ?????? ?????????? ???? ? 1212)( 121 tt kkkkrc ?， nkk t ????1 。 情況 2 ： 3?t ，且 t 是奇數(shù)。這類廣義 ?? 圖從最里的一對路徑 1Q 和 2Q 開始染色，直到最外的一對路徑 2?tQ 和 1?tQ ，這些染色方式按照本文介紹的方法進行染色。這里的問題只是在于還有一條單一 的路徑 tQ ，我們只需要使得這條路徑是一條彩虹路，就能夠保證整個廣義 ?? 圖彩虹連通。要使 tQ 是一條彩虹路，則這條路上的邊必須染不同的顏色，有 tk 個頂點，則需要 1?tk 種顏色。所以，這類的廣義 ?? 圖的彩虹連通數(shù) 11212)( 1221 ???????? ?????????? ???? ?? ttt kkkkkrc ?，nkk t ????1 。 無論是情況 1還是情況 2 ，按照本文方法進行的彩虹染色，得到的彩虹連通數(shù) )(?rc 都優(yōu)于 )(2 Grc 。綜上所述， n 個頂點的廣義 ?? 圖的彩虹連通數(shù)是： ???????????????????????? ???????????? ???????? ???.3,3,212。3,322。22)(21是奇數(shù)且是偶數(shù)且，tttjiktkktttjitkktkkrctjiji 其中， n 個頂點是指不計算端點 X 和 Y ，只是 t 條路徑上頂點的總數(shù)，即ji kkn ?? ， tji ???2 。 XXIX 第三章 結語 本文是課題是“特殊圖類的彩虹邊染色”，選取三類特殊圖。第一類是：度為 3 的 Halin 圖 xG ，按照本文的染色方法進行彩虹染色，使得圖 xH 是彩虹連通的，并計算出了這類圖的彩虹連通數(shù)， 423)( 2 ??? ?kkGrc ，其中 k 是層數(shù)，且3?k 。利用改善后的 ?3 連通圖的彩虹連通數(shù) 5 )1(3)( ?? nGrc 說明了 )( xGrc 是有意義的。第二類是：圈為 nC ，有 k 個內(nèi)部頂點的新輪圖 knW? ，按照本文的染色方法進行彩虹染色，使得圖 knW? 是彩虹連通的，并計算出了這類圖的彩虹連通數(shù)，kWrc kn ?? )( ，其中圈上頂點數(shù) 3?n ，內(nèi)部的頂點數(shù) 2?k 。并且說明了，當 8?n時，輪圖 8W 的彩虹連通數(shù)是 3)( 8 ?Wrc ，而增加一個內(nèi)部頂點，變成新輪圖 28?W ，雖然邊數(shù)增加 8 ，但是彩虹連通數(shù)卻是 2)( 28 ??Wrc ，比輪圖 8W 減少了 1。第三類是： n 個頂點的廣義 ?? 圖，按照本文的染色方法進行彩虹染色，使得廣義 ?? 圖是彩虹連通的，并計算出了這類圖的彩虹連通數(shù) )(?rc ，而現(xiàn)有的廣義 ?? 圖的彩虹連通數(shù)是 21)(2 ??? nnGrc 或 ，其中路徑數(shù) 3?t ，本文染色得出的 )(?rc 遠比現(xiàn)有的 )(2 Grc 優(yōu)異許多。 本文選取這三類特殊圖進行彩虹染色，也得到了相應的彩虹連通數(shù) )(Grc ，或許本文的染色方法并不是最優(yōu)異的，得到的彩虹連通數(shù) )(Grc 也不是最小的，這點是由于知識水平的有限，不能做到最優(yōu)秀，還望閱讀過本文的讀者給予意見，我會進一步改善染色方法，得到更優(yōu)的彩虹連通數(shù)。 XXX 參考文獻 [1]宋慧敏 吳建良 . Halin圖的均勻邊染色 [J]. 山東大學學報， 2020 38:3134； [2]董九英，李學良 .圖的彩虹連通數(shù)與最小度和 [J].中國科學：數(shù)學， 2020,43:714； [5]萬慧敏，史小藝，王艷麗 .幾種特殊圖的邊染色 [J].五邑大學學報， 2020 26:78； [6]苗蓮英 .圖的邊覆蓋染色 [D].山東大學博士論文， 2020 25:2124； [7],et al. Rainbow connection in graphs. Math Bohem， 2020。 [8]， to Graph Theory. Boston， 2020； [9]， . The Probabilistic Method. New York， 2020。 [10],et al. On rainbow connection. Electron J Combin 15, R57 (2020)。 [11]Chandran L， Das A， Rajendraprasad D， et connection number and connected dominating sets. J Graph Theory， 2020， 71： 206218。 [12]Xueliang Li, Yongtang connection in 3connected Graphs。 [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