کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646522 | 1632249 | 2016 | 10 صفحه PDF | دانلود رایگان |
Let GG be a nontrivial connected graph. For k∈Nk∈N, we define a coloring c:E(G)→{1,2,…,k}c:E(G)→{1,2,…,k} of the edges of GG such that adjacent edges can be colored the same. A path PP in GG is a rainbow path if no two edges of PP are colored the same. A rainbow path connecting two vertices uu and vv in GG is called rainbow uu–vv path. A graph GG is said rainbow-connected if for every two vertices uu and vv of GG, there exists a rainbow uu–vv path. In this case, the coloring cc is called a rainbow kk-coloring of GG. The minimum kk such that GG has a rainbow kk-coloring is called the rainbow connection number of GG.For t∈Nt∈N and t≥2t≥2, let {Gi|i∈{1,2,…,t}}{Gi|i∈{1,2,…,t}} be a finite collection of graphs and each GiGi has a fixed vertex voivoi called a terminal. The amalgamation Amal(Gi,voi)Amal(Gi,voi) is a graph formed by taking all the GiGi’s and identifying their terminals.We give lower and upper bounds for the rainbow connection number of Amal(Gi,voi)Amal(Gi,voi) for any connected graph GiGi. Additionally, we determine the rainbow connection number of amalgamation of either complete graphs, or wheels, or fans.
Journal: AKCE International Journal of Graphs and Combinatorics - Volume 13, Issue 1, April 2016, Pages 90–99