Rainbow connection number of amalgamation of some graphs

Abstract

Let G be a nontrivial connected graph. For k∈N, we define a coloring c:E(G)→{1,2,…,k} of the edges of G such that adjacent edges can be colored the same. A path P in G is a rainbow path if no two edges of P are colored the same. A rainbow path connecting two vertices u and v in G is called rainbow u–v path. A graph G is said rainbow-connected if for every two vertices u and v of G, there exists a rainbow u–v path. In this case, the coloring c is called a rainbow k-coloring of G. The minimum k such that G has a rainbow k-coloring is called the rainbow connection number of G. For t∈N and t≥2, let {Gi|i∈{1,2,…,t}} be a finite collection of graphs and each Gi has a fixed vertex voi called a terminal. The amalgamation Amal(Gi,voi) is a graph formed by taking all the Gi’s and identifying their terminals. We give lower and upper bounds for the rainbow connection number of Amal(Gi,voi) for any connected graph Gi. Additionally, we determine the rainbow connection number of amalgamation of either complete graphs, or wheels, or fans.

Keywords

• Amalgamation
• Complete graph
• Fan
• Rainbow connection number
• Wheel