Rainbow connection number of amalgamation of some graphs
D. Fitriani, A.N.M. Salman · AKCE International Journal of Graphs and Combinatorics · 2016
Let be a nontrivial connected graph. For , we define a coloring of the edges of such that adjacent edges can be colored the same. A path in is a rainbow path if no two edges of are colored the same. A rainbow path connecting two vertices and in is called rainbow – path. A graph is said rainbow-connected if for every two vertices and of , there exists a rainbow – path. In this case, the coloring is called a rainbow -coloring of . The minimum such that has a rainbow -coloring is called the rainbow connection number of .For and , let be a finite collection of graphs and each has a fixed vertex called a terminal. The amalgamation is a graph formed by taking all the ’s and identifying their terminals.We give lower and upper bounds for the rainbow connection number of for any connected graph . Additionally, we determine the rainbow connection number of amalgamation of either complete graphs, or wheels, or fans.